第 3 讲：递归式求解——代换法、递归树与主定理

一、递归式从哪里来

一个分治算法把规模 n 的问题拆成 a 个规模 n/b 的子问题，拆分与合并的代价为 f(n)，它的运行时间就满足

T(n) = a · T(n/b) + f(n)          a ≥ 1, b > 1
       └───┬────┘   └─┬─┘
        递归代价     分治代价

算法	递归式	解
二分查找	T(n) = T(n/2) + Θ(1)	Θ(log n)
归并排序	T(n) = 2T(n/2) + Θ(n)	Θ(n log n)
朴素矩阵乘法（分块）	T(n) = 8T(n/2) + Θ(n²)	Θ(n³)
Strassen	T(n) = 7T(n/2) + Θ(n²)	Θ(n^2.807)
快速排序（最坏）	T(n) = T(n−1) + Θ(n)	Θ(n²)
线性时间选择	T(n) = T(n/5) + T(7n/10) + Θ(n)	Θ(n)

两个技术性约定：

边界条件通常省略。只要 T(n) = Θ(1) 对足够小的 n 成立，它不影响渐近解。
下取整与上取整通常省略。写 T(n/2) 而不是 T(⌊n/2⌋)——可以证明（CLRS 4.6）这对本课程遇到的所有递归式都不改变渐近解。

二、方法一：代换法（Substitution）

两步：猜一个界，然后用数学归纳法证明它。

例：T(n) = 2T(n/2) + n

猜：T(n) = O(n log n)，即存在 c > 0 使 T(n) ≤ c·n log n。

归纳步骤：假设对所有 m < n 成立，特别地对 m = n/2：

T(n) ≤ 2 · (c·(n/2)·log(n/2)) + n
     = c·n·(log n − 1) + n
     = c·n·log n − c·n + n
     ≤ c·n·log n            只要 c ≥ 1  ✓

基础情形：n = 2 时 T(2) = 2T(1) + 2 是常数，取 c 足够大即可覆盖。（技巧：基础情形可以从任意足够大的 n₀ 开始，因为渐近记号只关心大 n。）∎

⚠️ 陷阱：不能"渐近地"做归纳

要证 T(n) = 2T(n/2) + n 是 O(n)，有人会写：

T(n) ≤ 2·(c·n/2) + n = c·n + n = O(n)   ✗ 错！

错在最后一步。归纳假设要求证出的是同一个常数 c 的 T(n) ≤ c·n，而我们只得到 (c+1)n。归纳必须精确地证明归纳假设的形式，不能中途换成 O 记号。 这个错误能"证明"出任何东西，是最常见的作业扣分点。

技巧：减去一个低阶项

要证 T(n) = 2T(n/2) + 1 是 O(n)。直接猜 T(n) ≤ cn：

T(n) ≤ 2·c·(n/2) + 1 = cn + 1    ✗ 差了一点，卡住

改猜更强的命题 T(n) ≤ cn − d（d > 0 是常数）：

T(n) ≤ 2(c·n/2 − d) + 1 = cn − 2d + 1 ≤ cn − d      只要 d ≥ 1  ✓

⭐ 反直觉但极其有用：证一个更强的命题反而更容易。 因为归纳假设也变强了。这个"减低阶项"的技巧在摊还分析（第 4 讲）里还会以势能函数的面貌出现。

三、方法二：递归树（Recursion Tree）

递归树用来猜答案，猜完再用代换法验证（或直接用主定理）。

例：T(n) = 3T(n/4) + n²

层    节点数    每节点代价       该层总代价
─────────────────────────────────────────────
0      1        n²                n²
1      3       (n/4)²            (3/16) n²
2      9       (n/16)²           (3/16)² n²
…      …         …                  …
i      3ⁱ      (n/4ⁱ)²           (3/16)ⁱ n²
…
log₄n  3^(log₄ n) = n^(log₄3)    Θ(n^0.793)   ← 叶子层

总代价：

T(n) = Σᵢ (3/16)ⁱ · n² + Θ(n^log₄3)
     ≤ n² · 1/(1 − 3/16) + o(n²)
     = Θ(n²)

观察：公比 3/16 < 1，几何级数被根部支配，叶子层可以忽略。这就是第 2 讲“等比级数被最大项支配"的直接应用。

三种形态

递归树的每层代价只可能是三种走势之一，这直接对应主定理的三种情形：

    ① 根部支配（递减）      ② 各层相等         ③ 叶子支配（递增）
    ████████████ n²        ██████ n           ██ 1
    ███ 3n²/16             ██████ n           ████ 2
    █ …                    ██████ n           ████████ 4
    总和 = Θ(根)            总和 = Θ(n log n)   总和 = Θ(叶子数)

⚠️ 递归树是启发式，不是证明。用它得到猜想后，正式作答要么补上代换法证明，要么套主定理。

不均匀分割：T(n) = T(n/3) + T(2n/3) + n

树不再平衡：最浅的叶子在深度 log₃ n，最深的在 log_{3/2} n。但每一层的代价仍然是 n（未触底的节点子问题规模之和仍为 n）。因此

T(n) ≤ n · log_{3/2} n = O(n log n)，且 T(n) ≥ n · log₃ n = Ω(n log n)
⟹ T(n) = Θ(n log n)

⭐ 这个例子解释了为什么快速排序即使分割不均匀（只要比例是常数），仍是 Θ(n log n)——见第 11 讲。

四、方法三：主定理（Master Theorem）

对形如

T(n) = a·T(n/b) + f(n)        a ≥ 1, b > 1, f(n) 渐近正

令 临界指数 为 log_b a，把 f(n) 与 n^(log_b a) 比较：

情形	条件	解	直觉
1	f(n) = O(n^(log_b a − ε))，某 ε > 0	T(n) = Θ(n^(log_b a))	叶子支配
2	f(n) = Θ(n^(log_b a) · log^k n)，k ≥ 0	T(n) = Θ(n^(log_b a) · log^(k+1) n)	各层均衡
3	f(n) = Ω(n^(log_b a + ε))，某 ε > 0，且正则条件 `a·f(n/b) ≤ c·f(n)`（某 c < 1，足够大的 n）	T(n) = Θ(f(n))	根部支配

n^(log_b a) 是什么？它就是递归树的叶子总数：树高 log_b n，每层分叉 a 倍，叶子数 = a^(log_b n) = n^(log_b a)。所以主定理在做的事非常朴素：比较"所有叶子的代价"和"根部的代价”，谁大听谁的；一样大就多乘一个 log。

例子演练

递归式	log_b a	f(n)	情形	解
T(n) = 9T(n/3) + n	log₃9 = 2	n = O(n^(2−ε))	1	Θ(n²)
T(n) = T(2n/3) + 1	log_{3/2}1 = 0	1 = Θ(n⁰)	2 (k=0)	Θ(log n)
T(n) = 2T(n/2) + n	log₂2 = 1	n = Θ(n¹)	2 (k=0)	Θ(n log n)
T(n) = 2T(n/2) + n log n	1	Θ(n·log n)	2 (k=1)	Θ(n log²n)
T(n) = 3T(n/4) + n log n	log₄3 ≈ 0.79	Ω(n^(0.79+ε)) ✓ 正则 ✓	3	Θ(n log n)
T(n) = 7T(n/2) + n²	log₂7 ≈ 2.807	n² = O(n^(2.807−ε))	1	Θ(n^2.807)
T(n) = 8T(n/2) + n²	log₂8 = 3	n² = O(n^(3−ε))	1	Θ(n³)

最后两行就是 Strassen 算法为什么快于朴素矩阵乘法：把 8 次递归乘法降到 7 次，临界指数从 3 降到 2.807（第 28 讲）。

⚠️ 主定理不适用的情形

（1）间隙（gap）：f(n) 比 n^(log_b a) 大，但不是多项式级别地大。

T(n) = 2T(n/2) + n log n     ← log₂2 = 1，f = n log n

n log n / n = log n，它不是 n^ε（对任何 ε > 0 都不是）。情形 1 和 3 都不适用。 好在这里落入了推广后的情形 2（k = 1），得 Θ(n log²n)。但对 T(n) = 2T(n/2) + n/log n 则三种情形全部不适用，必须用递归树硬算（答案是 Θ(n log log n)）。

（2）正则条件不满足：f(n) 波动剧烈时（如 f(n) = n²·sin²n），情形 3 的正则条件可能失效。

（3）子问题规模不同：T(n) = T(n/5) + T(7n/10) + n（第 13 讲的线性选择）不是主定理的形式。这类要用代换法或 Akra-Bazzi 定理。

（4）a 不是常数：T(n) = nT(n/2) + n 超出适用范围。

五、非分治型递归式

主定理只管 T(n/b)。减法型的递归式 T(n) = aT(n−c) + f(n) 要单独处理：

T(n) = T(n−1) + Θ(1)  ⟹  Θ(n)         线性查找、单链表遍历
T(n) = T(n−1) + Θ(n)  ⟹  Θ(n²)        快排最坏、选择排序
T(n) = 2T(n−1) + Θ(1) ⟹  Θ(2ⁿ)        汉诺塔、朴素枚举子集
T(n) = T(n−1) + T(n−2) ⟹  Θ(φⁿ)       朴素递归 Fibonacci（φ ≈ 1.618）
T(n) = nT(n−1)        ⟹  Θ(n!)        枚举全排列

⭐ 记住这条对照：除法型 T(n/2) 通常给出 log 级的树高，减法型 T(n−1) 给出 n 级的树高。 一个把规模砍半，一个只砍掉一个——这就是二分查找和线性查找的全部差别。

换元法

T(n) = 2T(√n) + log n 不像任何标准形式。令 m = log n（即 n = 2^m），设 S(m) = T(2^m)：

S(m) = 2S(m/2) + m      ⟹  主定理情形 2  ⟹  S(m) = Θ(m log m)
⟹  T(n) = Θ(log n · log log n)

六、求解流程图

        给定递归式 T(n)
              │
    ┌─────────┴──────────┐
    │ 是 aT(n/b) + f(n)？ │
    └─────┬────────┬─────┘
        是│        │否
          ▼        ▼
     ┌─────────┐  ┌────────────────────────┐
     │ 套主定理  │  │ 子问题不等规模？→ 递归树/代换 │
     └────┬────┘  │ 减法型？→ 直接展开        │
          │       │ 形状怪异？→ 换元          │
     ┌────┴────┐  └────────────────────────┘
     │ 落入某情形？│
     └──┬────┬──┘
      是│    │否（落在间隙里）
        ▼    ▼
      得解  画递归树猜 → 代换法证

随堂自测

用主定理求解：(a) T(n)=4T(n/2)+n　(b) T(n)=4T(n/2)+n²　(c) T(n)=4T(n/2)+n³。观察三个答案分别对应哪种情形，并说出主导层在哪。
T(n) = 2T(n/2) + n/log n 为什么主定理不适用？用递归树求出它的解。
用代换法证明 T(n) = T(n/2) + 1 是 O(log n)。为什么直接猜 T(n) ≤ c log n 在基础情形会出问题，该怎么修？
下面的"证明"错在哪：

设 T(n) = 2T(n/2) + n。归纳假设 T(n/2) = O(n/2)，则 T(n) = 2·O(n/2) + n = O(n)。
求解 T(n) = T(n/4) + T(3n/4) + n，并说明它与快速排序的关系。
T(n) = 3T(n/2) + n² 与 T(n) = 4T(n/2) + n² 的解分别是什么？为什么一个由根支配、一个各层均衡？
换元求解 T(n) = 2T(√n) + 1。

一、递归式从哪里来#

二、方法一：代换法（Substitution）#

例：T(n) = 2T(n/2) + n#

⚠️ 陷阱：不能"渐近地"做归纳#

技巧：减去一个低阶项#

三、方法二：递归树（Recursion Tree）#

例：T(n) = 3T(n/4) + n²#

三种形态#

不均匀分割：T(n) = T(n/3) + T(2n/3) + n#

四、方法三：主定理（Master Theorem）#

例子演练#

⚠️ 主定理不适用的情形#

五、非分治型递归式#

换元法#

六、求解流程图#

随堂自测#