渐近分析主定理（Master Theorem）详解

1. 简介

很多算法通过将一个大小为 n 的问题分解成多个更小的子问题来解决。这类算法中，最典型的是分治法（Divide-and-Conquer），例如二分查找（Binary Search）和归并排序（Merge Sort）。这类算法的运行时间通常可以用递归关系来建模。

本文将介绍主定理（Master Theorem），它是一种用于快速求解特定递归关系的工具，特别适用于形如：

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

的递归式，其中：

a ≥ 1：递归调用的子问题数量
b > 1：每个子问题的大小是原问题的 1/b
f(n)：将问题拆分和合并子问题所需的额外工作量

2. 主定理的表述

考虑一个算法，它通过以下方式解决大小为 n 的问题：

将问题分成 a 个子问题，每个子问题大小为 n/b
递归地解决 a 个子问题
合并这些子问题的解

设 T(n) 表示解决大小为 n 的问题所需的总工作量，f(n) 表示拆分和合并阶段的代价。则递归关系如下：

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

2.1. 没有额外工作量的情况

假设 f(n) = 0，即：

T(n) = aT(n/b)

可以画出递归树来表示每层的工作量：

递归树示意图

递归树的高度为 log_b(n)，在第 i 层有 a^i 个节点。最终叶子节点数为 a^{log_b(n)} = n^{log_b(a)}，因此总时间为：

T(n) = Θ(n^{log_b(a)})

2.2. 主定理内容

对于递归式：

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

若 a ≥ 1, b > 1，且 f(n) 是渐近正函数，则以下三种情况成立：

✅ Case 1：若 f(n) = O(n^{log_b(a) - ε})，对某个 ε > 0 成立，则：
```
T(n) = Θ(n^{log_b(a)})
```
✅ Case 2：若 f(n) = Θ(n^{log_b(a)})，则：
```
T(n) = Θ(n^{log_b(a)} log n)
```
✅ Case 3：若 f(n) = Ω(n^{log_b(a) + ε})，对某个 ε > 0 成立，且满足 正则条件（regularity condition）：
```
af(n/b) ≤ c f(n)，其中 c < 1
```
则：
```
T(n) = Θ(f(n))
```

2.3. 多项式大 vs 渐近大

主定理并不适用于所有 f(n)。如果 f(n) 与 n^{log_b(a)} 之间相差的不是多项式因子，则无法使用主定理。

📌 多项式大：f(n) 是 g(n) 的多项式大，当且仅当存在两个多项式 p(n) 和 q(n)，使得：

p(n) ≤ f(n)/g(n) ≤ q(n)

📌 渐近大但非多项式大的例子：

n log n 是 n 的渐近大，但不是多项式大，因为 log n 增长不够快。
e^n 是 n^1000 的渐近大，但也不是多项式大，因为增长太快。

3. 示例分析

示例 1

T(n) = 9T(n/3) + n

a = 9, b = 3, f(n) = n
n^{log_b(a)} = n^{log_3(9)} = n^2

f(n) = n 是 n^2 的多项式小，符合 Case 1：

✅ 结果：T(n) = Θ(n^2)

示例 2

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

a = 1, b = 3/2, f(n) = 1
n^{log_b(a)} = n^{log_{3/2}(1)} = n^0 = 1

f(n) = 1 与 n^0 增长相同，符合 Case 2：

✅ 结果：T(n) = Θ(log n)

示例 3

T(n) = 3T(n/4) + n log n

a = 3, b = 4, f(n) = n log n
n^{log_b(a)} = n^{log_4(3)} ≈ n^0.7925

f(n) = n log n 是 n^0.7925 的多项式大，符合 Case 3：

✅ 结果：T(n) = Θ(n log n)

示例 4（主定理不适用）

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

a = 2, b = 2, f(n) = n log n
n^{log_b(a)} = n^{log_2(2)} = n

f(n) = n log n 是 n 的渐近大，但不是多项式大（因为 log n 不是多项式因子），因此 主定理不适用。

❌ 结论：不能使用主定理求解

4. 主定理的证明思路（简要）

递归式：

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

可以构建递归树：

根节点代价为 f(n)
每层有 a^j 个节点，每个节点代价为 f(n/b^j)
总代价为：

T(n) = Θ(n^{log_b(a)}) + ∑_{j=0}^{log_b(n)-1} a^j f(n/b^j)

第一项是叶子节点总代价
第二项是内部节点总代价

主定理的核心在于比较 f(n) 和 n^{log_b(a)} 的增长速度。

5. 总结

主定理是一个用于快速求解特定递归式时间复杂度的强大工具，特别适用于分治类算法。

📌 关键点：

主定理适用于 T(n) = aT(n/b) + f(n) 形式的递归
核心是比较 f(n) 和 n^{log_b(a)}
只有当 f(n) 是 n^{log_b(a)} 的多项式小或大时才适用
若两者之间差距不是多项式因子（如 n log n vs n），则主定理不适用

✅ 适用场景：

快速排序（Quick Sort）
归并排序（Merge Sort）
矩阵乘法分治（Strassen）
二分查找（Binary Search）

❌ 不适用场景：

f(n) 与 n^{log_b(a)} 差距非多项式（如 n log n、e^n）

📌 踩坑提醒：

不要盲目套用主定理，先验证是否满足其适用条件
对于 Case 3，一定要检查正则条件是否成立
注意 log_b(a) 的计算精度，避免误判

主定理是分析递归算法时间复杂度的重要工具，掌握它能显著提升算法分析效率。

Persistence

REST

Security