文章目录
- 📝 算法复杂度分析笔记：主定理详解
- 1. 题目回顾
- 2. 核心工具：主定理 (Master Theorem)
- 🔑 参数含义
- ⚖️ 比较逻辑
- 3. 解题步骤演示
- 第一步：提取参数
- 第二步：计算临界值
- 第三步：比较f ( n ) f(n)f(n)与n log b a n^{\log_b a}nlogba
- 第四步：匹配主定理情况
- 第五步：得出结论
- 4. 知识拓展：主定理的三种情况总结
- 本题为何不是其他选项？
- 5. 易错点提示
📝 算法复杂度分析笔记：主定理详解
1. 题目回顾
问题：某递归算法的时间复杂度计算公式为T ( n ) = 4 T ( n / 2 ) + n lg n T(n) = 4T(n/2) + n\lg nT(n)=4T(n/2)+nlgn，求该算法的时间复杂度。
选项：
A.O ( n lg n ) O(n\lg n)O(nlgn)
B.O ( n 3 ) O(n^3)O(n3)
C.O ( n 2 ) O(n^2)O(n2)
D.O ( n 2 lg n ) O(n^2 \lg n)O(n2lgn)
2. 核心工具：主定理 (Master Theorem)
主定理是解决分治算法时间复杂度的“万能公式”。它专门处理形式为以下的递归方程：
T ( n ) = a T ( n / b ) + f ( n ) T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n)
🔑 参数含义
- n nn：问题规模。
- a aa：递归产生的子问题个数（a ≥ 1 a \ge 1a≥1）。
- b bb：每个子问题的规模缩小倍数（b > 1 b > 1b>1）。即子问题规模是原问题的1 / b 1/b1/b。
- f ( n ) f(n)f(n)：除了递归调用外，当前层所做的额外工作（如分解问题和合并结果的时间）。
⚖️ 比较逻辑
主定理的核心思想是比较“子问题的总代价”(n log b a n^{\log_b a}nlogba) 与“当前层的额外工作”(f ( n ) f(n)f(n)) 谁大谁小。
我们需要计算一个关键值：临界指数E = log b a E = \log_b aE=logba。
3. 解题步骤演示
针对本题T ( n ) = 4 T ( n / 2 ) + n lg n T(n) = 4T(n/2) + n\lg nT(n)=4T(n/2)+nlgn，我们按以下步骤操作：
第一步：提取参数
对比标准公式，找出a , b , f ( n ) a, b, f(n)a,b,f(n)：
- a = 4 a = 4a=4（有4个子问题）
- b = 2 b = 2b=2（规模减半）
- f ( n ) = n lg n f(n) = n\lg nf(n)=nlgn（额外工作量）
第二步：计算临界值
计算叶子节点（子问题）的增长率：
n log b a = n log 2 4 = n 2 n^{\log_b a} = n^{\log_2 4} = n^2nlogba=nlog24=n2
💡 思考点：log 2 4 \log_2 4log24等于多少？因为2 2 = 4 2^2 = 422=4，所以log 2 4 = 2 \log_2 4 = 2log24=2。这意味着如果不考虑合并成本，光看子问题数量，复杂度就是平方级的。
第三步：比较f ( n ) f(n)f(n)与n log b a n^{\log_b a}nlogba
现在我们需要比较f ( n ) = n lg n f(n) = n\lg nf(n)=nlgn和n 2 n^2n2的大小关系。
- f ( n ) f(n)f(n)是n nn乘以对数。
- n log b a n^{\log_b a}nlogba是n nn的平方。
显然，当n nn趋向无穷大时，n 2 n^2n2的增长速度远快于n lg n n\lg nnlgn。
用数学语言描述：存在ϵ > 0 \epsilon > 0ϵ>0（例如取ϵ = 0.5 \epsilon=0.5ϵ=0.5），使得f ( n ) = O ( n 2 − ϵ ) f(n) = O(n^{2-\epsilon})f(n)=O(n2−ϵ)。
第四步：匹配主定理情况
根据比较结果，我们落入情况 1：
- 条件：如果f ( n ) f(n)f(n)多项式地小于n log b a n^{\log_b a}nlogba（即子问题代价占主导地位）。
- 结论：总复杂度由子问题代价决定，即T ( n ) = Θ ( n log b a ) T(n) = \Theta(n^{\log_b a})T(n)=Θ(nlogba)。
第五步：得出结论
因为n 2 n^2n2占主导地位，所以：
T ( n ) = Θ ( n 2 ) T(n) = \Theta(n^2)T(n)=Θ(n2)
对应选项C。
4. 知识拓展：主定理的三种情况总结
为了方便记忆，可以将主定理想象成一场“拔河比赛”：一方是n log b a n^{\log_b a}nlogba（子问题），另一方是f ( n ) f(n)f(n)（额外工作）。
| 情况 | 谁更强？ | 数学条件 | 最终复杂度 | 记忆口诀 |
|---|---|---|---|---|
| Case 1 | 子问题强 | f ( n ) = O ( n log b a − ϵ ) f(n) = O(n^{\log_b a - \epsilon})f(n)=O(nlogba−ϵ) | Θ ( n log b a ) \Theta(n^{\log_b a})Θ(nlogba) | 叶子重，看叶子 |
| Case 2 | 势均力敌 | f ( n ) = Θ ( n log b a lg k n ) f(n) = \Theta(n^{\log_b a} \lg^k n)f(n)=Θ(nlogbalgkn) | Θ ( n log b a lg k + 1 n ) \Theta(n^{\log_b a} \lg^{k+1} n)Θ(nlogbalgk+1n) | 一样重，乘个lg n \lg nlgn |
| Case 3 | 根节点强 | f ( n ) = Ω ( n log b a + ϵ ) f(n) = \Omega(n^{\log_b a + \epsilon})f(n)=Ω(nlogba+ϵ) | Θ ( f ( n ) ) \Theta(f(n))Θ(f(n)) | 根节点重，看根节点 |
本题为何不是其他选项？
- A.O ( n lg n ) O(n\lg n)O(nlgn)：这是f ( n ) f(n)f(n)本身的复杂度。只有当f ( n ) f(n)f(n)占主导（Case 3）时才选这个，但这里n 2 n^2n2比它大。
- D.O ( n 2 lg n ) O(n^2 \lg n)O(n2lgn)：这是 Case 2 的结果。只有当f ( n ) f(n)f(n)恰好等于n 2 n^2n2或者n 2 lg n n^2 \lg nn2lgn这种级别时才会出现。这里n lg n n\lg nnlgn比n 2 n^2n2小太多了，还没法“势均力敌”。
5. 易错点提示
- 不要只看f ( n ) f(n)f(n)：很多同学看到n lg n n\lg nnlgn就直接选 A，忽略了前面的4 T ( n / 2 ) 4T(n/2)4T(n/2)产生的巨大开销。
- 准确计算对数：log b a \log_b alogba算错会导致全盘皆输。例如若误算成log 2 4 = 1 \log_2 4 = 1log24=1，就会得出错误结论。
- 区分n lg n n\lg nnlgn和n 2 n^2n2：在渐进复杂度中，多项式级（n x , x > 1 n^x, x>1nx,x>1）永远大于线性对数级（n lg n n\lg nnlgn）。
