递归

题目：递归算法时间复杂度分析

1. 题目描述

给定一个递归算法的时间复杂度表达式：

• 当 $n \le 1$ 时，$T(n) = 0$
• 当 $n > 1$ 时，$T(n) = 8T(\frac{n}{2}) + 2n^3 + 3n^2$

则该算法的时间复杂度为（ ）

A. $O(n^3)$
B. $O(n^3 \log n)$
C. $O(n^4)$
D. $O(n^4 \log n)$

正确答案：B

---

2. 核心考点：主定理 (Master Theorem)

对于形如 $T(n) = aT(\frac{n}{b}) + f(n)$ 的递归式，我们可以通过比较 $f(n)$ 与 $n^{\log_b a}$ 的阶级来确定复杂度。

本题推导过程：

1. 确定参数：

   • $a = 8$ （递归子问题的数量）
   • $b = 2$ （每个子问题的规模缩小比例）
   • $f(n) = 2n^3 + 3n^2$ （合并子问题所需的额外工作）

2. 简化 $f(n)$： 在渐进复杂度分析中，只保留最高次项，故 $f(n) = O(n^3)$。即 $d = 3$。

3. 计算关键项 $n^{\log_b a}$：

$$\log_b a = \log_2 8 = 3$$

因此，关键项为 $n^3$。

4. 比较与结论： 由于 $f(n) = O(n^3)$ 且 $n^{\log_b a} = n^3$，两者同阶（满足主定理的第二种情况）。 根据公式，当两者同阶时：

$$T(n) = O(n^{\log_b a} \cdot \log n) = O(n^3 \log n)$$

---

3. 知识点总结（快速查表）

情况	关系	复杂度结论
Case 1	$f(n) < n^{\log_b a}$	$T(n) = O(n^{\log_b a})$
Case 2	$f(n) = n^{\log_b a}$	$T(n) = O(n^{\log_b a} \log n)$
Case 3	$f(n) > n^{\log_b a}$	$T(n) = O(f(n))$

---