#
chat
基本介绍
递归复杂度计算中确实有一个非常常用的工具，叫做 Master Theorem（主定理），可以用来分析形如分治递归的时间复杂度，非常适合处理像归并排序、快速排序、二分法、树型递归等场景。
一、Master Theorem（主定理）公式
它适用于如下形式的递归关系：
T(n) = a * T(n/b) + f(n)
其中：
a：每次递归分成的子问题数n/b：每个子问题的规模f(n)：除递归外，当前层的其他操作开销（比如合并、遍历等）
二、主定理的三种情况
根据 f(n) 和 n^log_b(a) 的大小关系，有三种情况：
情况 1：f(n) 比 n^log_b(a) 小
- 如果：
f(n) = O(n^c)，且c < log_b(a) - 则：
T(n) = Θ(n^log_b(a))
✅ 此时递归的子问题主导复杂度。
情况 2：f(n) 与 n^log_b(a) 相等
- 如果：
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) 大
- 如果：
f(n) = Ω(n^c)，且c > log_b(a)，并满足“正则性条件” - 则：
T(n) = Θ(f(n))
👉 正则性条件：a * f(n/b) ≤ k * f(n)，其中 k < 1，成立时才可以用。
✅ 此时本层的操作主导复杂度。
三、几个经典例子
✅ 示例 1：归并排序
T(n) = 2T(n/2) + O(n)
- a = 2，b = 2，f(n) = O(n)
- log_b(a) = log₂2 = 1
- f(n) = Θ(n)，等于 n^1
➡ 属于情况 2 ➡ 所以 T(n) = Θ(n log n)
✅ 示例 2：二分查找
T(n) = T(n/2) + O(1)
- a = 1，b = 2，f(n) = O(1)
- log₂1 = 0
- f(n) = Θ(1)，等于 n^0
➡ 属于情况 2 ➡ 所以 T(n) = Θ(log n)
✅ 示例 3：暴力斐波那契
T(n) = T(n - 1) + T(n - 2) + O(1)
这个不符合 Master Theorem格式（不是 n/b），就不能用主定理。
➡ 这类递归要用“递归树分析法”，复杂度约为 O(2^n)。
四、常见算法的递归关系
| 算法 | 递归公式 | 时间复杂度 |
|---|---|---|
| 归并排序 | T(n) = 2T(n/2) + O(n) | Θ(n log n) |
| 快速排序（平均） | T(n) = 2T(n/2) + O(n) | Θ(n log n) |
| 快速排序（最坏） | T(n) = T(n - 1) + O(n) | O(n²) |
| 二分查找 | T(n) = T(n/2) + O(1) | O(log n) |
| Karatsuba乘法 | T(n) = 3T(n/2) + O(n) | O(n^log₂3) ≈ O(n^1.59) |
五、小结口诀
📌 主定理口诀版总结：
T(n) = a T(n/b) + f(n)
比较 f(n) 与 n^log_b(a)：
- 小于：复杂度由递归决定（情况 1）
- 等于：复杂度加 log（情况 2）
- 大于：复杂度由本层决定（情况 3，需正则性）
