14.2.2 时间复杂度与空间复杂度-02

本节把复杂度推进到递归式。课程重点不是要求你掌握所有递归求解技巧，而是认识主定理适用的形式，并会对常见增长阶做比较。

递归式形式

典型分治递归式：

$$T(n)=aT(n/b)+f(n)$$

其中：

符号	含义
$a$	子问题个数
$n/b$	每个子问题规模
$f(n)$	分解和合并等额外工作

主定理只适用于这种“规模按比例缩小”的形式。若是 $T(n)=T(n-1)+...$，不能直接套主定理。

主定理的比较核心

比较 $f(n)$ 与：

$$n^{{\log }_{b}a}$$

如果 $f(n)$ 更小，复杂度主要由递归子问题决定；如果同阶，会多一个 $\log n$；如果 $f(n)$ 更大且满足正则条件，复杂度主要由 $f(n)$ 决定。

例：$T(n)=8T(n/2)+n^2$

这里 $a=8,b=2,f(n)=n^2$。

$$n^{{\log }_{b}a}=n^{{\log }_{2}8}=n^3$$

因为 $n^2$ 小于 $n^3$，所以：

$$T(n)=O(n^3)$$

复杂度比较题

比较增长阶时，先把常数去掉，再按增长序排：

$$\log n<n^{2/3}<n<n^4<2^n<n!$$

课程例题中 1000n 的量级仍然是 $O(n)$，不会因为系数 1000 就超过 $n^2$。

空间复杂度补充

递归除了时间成本，还有调用栈空间。若递归深度为 $h$，每层只用常量辅助变量，则栈空间约为 $O(h)$。例如二分递归深度是 $O(\log n)$，单支递归深度可能是 $O(n)$。

本节例题

单选

递归式 $T(n)=8T(n/2)+n^2$ 的时间复杂度为：

AO(n)BO(n²)CO(n³)DO(2ⁿ)

自查清单

1. 能否判断主定理是否适用于某个递归式？
2. 能否计算 $n^{{\log }_{b}a}$ 并与 $f(n)$ 比较？
3. 能否解释为什么递归调用栈也会占用空间？