CSP-S 2025 第一轮 第11题：递归关系式 T(n) = 2T(n/2) + O(n^2) 描述了某个分治算法的

题目

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

选项

• A. $O(n)$
• B. $O(n \log n)$
• C. $O(n^2)$
• D. $O(n^2 \log n)$

答案

C

题解

答案是 C. \(O(n^2)\)。

用递归树理解：

• 第 0 层：1 个规模为 \(n\) 的问题，额外耗时 \(O(n^2)\)。
• 第 1 层：2 个规模为 \(n/2\) 的问题，总耗时 \(2\cdot O((n/2)^2)=O(n^2/2)\)。
• 第 \(i\) 层：\(2^i\) 个规模为 \(n/2^i\) 的问题，总耗时 \(O(n^2/2^i)\)。

各层耗时相加是等比数列： \[ T(n)=O\left(n^2\left(1+\frac12+\frac14+\cdots\right)\right)=O(n^2). \]

虽然递归有 \(\log n\) 层，但每层耗时都减半，所以不需要再乘 \(\log n\)。