本文最后更新于：2025年11月29日下午

【一周一算法】第六周：分治算法通论 · 主定理（Master Theorem）全解析

“当你理解主定理那一刻，你会发现所有递归算法的时间复杂度其实都在同一个维度体系里。” ——算法导论（CLRS）

上周我们讲了 二分查找。你已经看到一种“把问题规模缩小一半”的威力：从 O(n) → O(log n)，效率是天与地的差别。

但：

二分查找 是把问题规模分成 1 个子问题（规模 n/2）。
归并排序 是分成 2 个子问题（n/2）。
快速幂 是 1 个（n/2）。
Strassen 矩阵乘法 是 7 个（n/2）。
T(n) = 3T(n/4) + n 又是什么复杂度？

这些算法都可以用一句话统一起来：

分治（Divide & Conquer）= 拆分 → 递归 → 合并

那么，分治复杂度如何推导？这就是今天的主角：

🧩 一、主定理（Master Theorem）是什么？

主定理就是：

写成 T(n) = aT(n/b) + f(n) 的递归式 可以直接由比较 a 与 b^k（其中 k 来自 f(n)）来判断复杂度。

它能一刀切地解决绝大多数分治算法的时间复杂度问题。

不用展开递归不用画递归树不用推无穷级数只需要——一个公式

🧭 二、分治算法一般形式

所有分治算法可以写成这个形式：

T(n)=aT\left(\frac{n}{b}\right)+f(n)

含义如下：

参数	意义
a	子问题个数
b	每个子问题的规模缩小因子
f(n)	合并时的消耗（如 merge、partition、额外扫描）

例子看看：

算法	a	b	f(n)	复杂度
二分查找	1	2	O(1)	O(log n)
归并排序	2	2	O(n)	O(n log n)
快速排序（平均）	2	2	O(n)	O(n log n)
快速幂	1	2	O(1)	O(log n)
Strassen	7	2	O(n^2)	O(n^log₂7)≈O(n^2.81)

你有没有发现？

这些结果就是主定理直接算出来的！

🎯 三、主定理完整版（你只需记住一个对比）

主定理把情况分成三类，核心就一句话：

比较 f(n) 与 n^{log_b a} 的大小。

把 $k = \log_b a$

代入后比较：

情况	比较结果	复杂度
Case 1	f(n) = O(n^{k-ε}) → 合并比递归弱	T(n) = Θ(n^k)
Case 2	f(n) = Θ(n^k log^m n)	T(n) = Θ(n^k log^{m+1} n)
Case 3	f(n) = Ω(n^{k+ε}) → 合并比递归强	T(n) = Θ(f(n))（需正则性条件）

其实你只需要记住 Case 1–3 的“谁大谁赢”原则。

我们马上用经典例子说明。

🧪 四、经典例子：用主定理一秒算复杂度

🔹 示例 1：归并排序

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

a = 2
b = 2 → k=log₂2=1
f(n)=n → 是 n¹

完全符合 Case 2

⭐ 结果：

T(n) = Θ(n log n)

你是不是觉得这太快了？

🔹 示例 2：二分查找

T(n)=1T(n/2)+1

a = 1
b = 2 → k= log₂1 = 0
f(n)=1 → n⁰

Case 2 再次命中。

⭐ 结果：

T(n) = Θ(log n)

🔹 示例 3：Strassen 矩阵乘法

T(n)=7T(n/2)+n^2

a = 7
b = 2 → k = log₂7 ≈ 2.807
f(n)=n² → 比 n^{2.807} 小

命中 Case 1

⭐ 结果：

T(n) = Θ(n^{log₂7}) ≈ Θ(n^{2.81})

🔹 示例 4：T(n)=3T(n/4)+n

经典难题！

a = 3
b = 4
k = log₄3 ≈ 0.792
f(n)=n

n¹ 比 n⁰․⁷⁹² 强，命中 Case 3

⭐ 结果：

T(n)=Θ(n)

分治算法的复杂度竟然是线性的！

这就是主定理的力量。

🧰 五、代码示例：递归复杂度验证（C++）

为了更直观，我们写一个简单递归计数器，模拟：

1	`T(n) = 2T(n/2) + n`

看看它是否真是 O(n log n)

#include <iostream>
#include <chrono>

long long mergeSortCost(int n) {
    if (n <= 1) return 1;

    long long left = mergeSortCost(n / 2);
    long long right = mergeSortCost(n / 2);

    return left + right + n; // f(n) = n
}

int main() {
    for (int n : {128, 256, 512, 1024, 2048, 4096}) {
        auto cost = mergeSortCost(n);
        std::cout << "n=" << n << ", cost=" << cost << std::endl;
    }
    return 0;
}

输出成本基本满足：

n 翻倍 → cost 接近乘上 (log n + 1) 的比例符合 O(n log n)。

📈 六、递归树视角：为什么主定理这么准？

主定理背后的直觉其实超简单：

把递归拆成 3 层开销：

顶层：一次 f(n)
第二层：a 次 f(n/b)
第三层：a² 次 f(n/b²)
…
最底层：n → 1 时的单元成本

a/b^k 决定“是否爆炸” 而 f(n) 决定“合并是否是瓶颈”。

总结成一句话：

递归树越宽 → 越像 n^k 合并越强 → 越像 f(n) 差不多大 → 多一个 log n

这就是主定理的三大 case 来源。

🔍 七、主定理的使用禁区（非常重要）

⚠ 主定理不能应用在这些情况：

❌ b 不是常数

例如： T(n) = T(n - 1) + T(n - 2) （斐波那契）

❌ aT(n/b) 中，规模不是 n/b 类型

如： T(n) = T(n/2) + T(n/3) + n （需要 Akra–Bazzi 定理）

❌ f(n) 包含非多项式项

如： T(n) = 2T(n/2) + n / log n

主定理“不吃”这种形式。

🧠 八、思考题与练习

延续我们的一贯风格：你可以用主定理试着推导以下式子的复杂度。

❓ 1. T(n) = 4T(n/2) + n

提示：

a=4, b=2 → k=log₂4=2
f(n)=n

❓ 2. T(n) = 9T(n/3) + n² log n

提示：

f(n) 比 n^{log₃9} 稍大

❓ 3. T(n) = 2T(n/4) + √n

提示：

a=2, b=4 → k=log₄2=0.5
f(n)=n^{0.5}

这些练习可以加深你对三大 Case 的理解。

🌱 九、延伸阅读

《算法导论》第 4 章：Master Theorem
MIT 6.046：Divide and Conquer 课程讲义
Akra-Bazzi 定理：主定理的更强版本

✨ 十、总结

内容	结论
分治算法	递归拆分 + 合并
主定理	通过比较 f(n) 与 n^{log_b a} 决定复杂度
Case 1	递归占主导
Case 2	递归与合并同级 → 多一个 log
Case 3	合并占主导
适用范围	只适用于 T(n)=aT(n/b)+f(n) 类型