CSP-S 提高级 · CSP 2025 提高级第一轮 第 11 题

递归关系式 $T(n) = 2T(n/2) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

拿到递推式先别急着套公式，把a、b、f(n)三个参数拎出来，算一下log_b a和f(n)的指数对比，主定理三种情况一眼就能定乾坤。

学生最容易把这道题和归并排序搞混，因为形式太像了，都是2T(n/2)开头，但归并排序是O(n)的合并，这道题是O(n²)的合并，主导项完全不同。还有人会惯性思维觉得分治就是O(n log n)，或者误判f(n)和n^log_b a的大小关系导致选错情况。

这道题考的是算法分析里的主定理（Master Theorem），这是处理分治递推式 T(n)=aT(n/b)+f(n) 的万能钥匙。命题人喜欢挖的坑就是参数看走眼——比如把 f(n) 的复杂度看错，或者算错 log_b a。拿到题先别慌，把 a、b、f(n) 三个参数拎出来：这里 a=2，b=2，f(n)=O(n²)。关键一步是算 log_b a = log₂2 = 1。现在比较 f(n) 和 n^{log_b a} = n¹：显然 n² 比 n 大得多，满足第三种情况 f(n) = Ω(n^{log_b a + ε})（ε=1）。因此 T(n) = Θ(f(n)) = O(n²)。用递归树验证更直观：第0层 n²，第1层 2×(n/2)² = n²/2，第2层 4×(n/4)² = n²/4……加起来是个收敛的几何级数 2n²，还是 O(n²)。避坑提醒：一定要和归并排序的 T(n)=2T(n/2)+O(n) 区分开，后者是第二种情况，结果才是 O(n log n)。这类题在竞赛里很常见，2024年考过17题、2025年14题、2026年15题，说明命题人持续喜欢用分治递推式考主定理。预测未来大概率还会考这种“一眼看出 f(n) 主导”的题型，或者变着花样把 f(n) 改成 n·log n 之类需要仔细比较指数的陷阱。