第 2 课｜递归树与 Master Theorem
阅读提示：这是从聊天授课内容重构的课程讲义，不是原消息的逐字拷贝。建议先阅读概念动画，再跟随推导、数值算例和练习巩固知识。
学习问题
关键是计算递归树每一层所有节点的成本，而不只是沿一条递归路径求和。
[[diagram:recursion]]
核心公式
\[T(n)=a T(n/b)+f(n); layer_i=a^i f(n/b^i)\]数值例题
对 T(n)=2T(n/2)+n，所有内部层的工作量均为 n，深度 log₂n，因此 T(n)=Θ(n log n)。如果额外工作变为 n²，每层为 n²/2^i，根层主导，T(n)=Θ(n²)。
推导、假设与边界
定义 p=log_b a；若 f(n)=Θ(n^d)，当 d<p，叶层主导，T(n)=Θ(n^p)；当 d=p，各层相当，T(n)=Θ(n^p log n)；当 d>p，根层主导，T(n)=Θ(n^d)。标准 Master 定理有正则条件，不能机械套用。
Master Theorem 背后的等比级数
对 $T(n)=aT(n/b)+cn^d$，第 $i$ 层的总额外工作：
\[W_i=a^ic(n/b^i)^d=cn^d(a/b^d)^i.\]定义 $r=a/b^d$。当 $r>1$，下层增长，叶节点附近的工作主导；$r=1$ 时所有层一样；$r<1$ 时根部附近主导。这与机械记忆三种结论相比，多了一层可迁移的判断力：任一层整体工作量与相邻层相比如何变化？
正则性条件为什么存在？
标准 Master 第三种情形通常要求：
\[a f(n/b)\leq c f(n),\qquad 0<c<1.\]它保证递归子问题层的总额外成本相对父节点有稳定下降。若 $f(n)$ 在不同规模间剧烈振荡，仅知道它整体增长得快于 $n^p$ 可能无法自动得到根主导。
Master 无法直接使用怎么办？
例如：
\[T(n)=2T(n/2)+\frac{n}{\log_2 n}.\]令 $h=\log_2 n$，第 $i$ 层总成本 $n/(h-i)$，内层求和：
\[\sum_{i=0}^{h-1}\frac{n}{h-i}=nH_h=\Theta(n\log h).\]由于 $h=\log n$，故递归总成本是 $\Theta(n\log\log n)$。这种例子提醒我们：必须注意 $f(n)$ 与 $n^p$ 相差的是固定多项式因子还是对数因子。
时间与空间另行分析
归并排序总工作量 $\Theta(n\log n)$，但递归调用栈深度只有 $\Theta(\log n)$；典型实现的辅助归并数组额外需要 $\Theta(n)$ 空间。如果子问题并行运行，还要进一步分析 Work 与 Span，而不是只用顺序总工作量推算并行完成时间。
课后练习（暂不提供答案）
练习：分别分析 4T(n/2)+n、4T(n/2)+n²、4T(n/2)+n³，并验证第三个递推的正则性条件。
后续学习
沿各门课 12 周知识树继续递进，必要时回顾本课基本概念。