算法复杂度分析笔记：主定理详解

📝 算法复杂度分析笔记：主定理详解

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}nlogb​a) 与“当前层的额外工作”(f ( n ) f(n)f(n)) 谁大谁小。

我们需要计算一个关键值：临界指数E = log ⁡ b a E = \log_b aE=logb​a。

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^2nlogb​a=nlog2​4=n2

💡 思考点：log ⁡ 2 4 \log_2 4log2​4等于多少？因为2 2 = 4 2^2 = 422=4，所以log ⁡ 2 4 = 2 \log_2 4 = 2log2​4=2。这意味着如果不考虑合并成本，光看子问题数量，复杂度就是平方级的。

第三步：比较f ( n ) f(n)f(n)与n log ⁡ b a n^{\log_b a}nlogb​a

现在我们需要比较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}nlogb​a是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}nlogb​a（即子问题代价占主导地位）。
• 结论：总复杂度由子问题代价决定，即T ( n ) = Θ ( n log ⁡ b a ) T(n) = \Theta(n^{\log_b a})T(n)=Θ(nlogb​a)。

第五步：得出结论

因为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}nlogb​a（子问题），另一方是f ( n ) 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. 易错点提示

1. 不要只看f ( n ) f(n)f(n)：很多同学看到n lg ⁡ n n\lg nnlgn就直接选 A，忽略了前面的4 T ( n / 2 ) 4T(n/2)4T(n/2)产生的巨大开销。
2. 准确计算对数：log ⁡ b a \log_b alogb​a算错会导致全盘皆输。例如若误算成log ⁡ 2 4 = 1 \log_2 4 = 1log2​4=1，就会得出错误结论。
3. 区分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）。