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

文章目录 算法复杂度分析笔记主定理详解1. 题目回顾2. 核心工具主定理 (Master Theorem) 参数含义⚖️ 比较逻辑3. 解题步骤演示第一步提取参数第二步计算临界值第三步比较f ( n ) f(n)f(n)与n log ⁡ b a n^{\log_b a}nlogb​a第四步匹配主定理情况第五步得出结论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 1b1。即子问题规模是原问题的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 aElogb​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 4a4有4个子问题b 2 b 2b2规模减半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​anlog2​4n2 思考点log ⁡ 2 4 \log_2 4log2​4等于多少因为2 2 4 2^2 4224所以log ⁡ 2 4 2 \log_2 4 2log2​42。这意味着如果不考虑合并成本光看子问题数量复杂度就是平方级的。第三步比较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 \epsilon0.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)额外工作。情况谁更强数学条件最终复杂度记忆口诀Case 1子问题强f ( n ) O ( n log ⁡ b a − ϵ ) f(n) O(n^{\log_b a - \epsilon})f(n)O(nlogb​a−ϵ)Θ ( n log ⁡ b a ) \Theta(n^{\log_b a})Θ(nlogb​a)叶子重看叶子Case 2势均力敌f ( n ) Θ ( n log ⁡ b a lg ⁡ k n ) f(n) \Theta(n^{\log_b a} \lg^k n)f(n)Θ(nlogb​algkn)Θ ( n log ⁡ b a lg ⁡ k 1 n ) \Theta(n^{\log_b a} \lg^{k1} n)Θ(nlogb​algk1n)一样重乘个lg ⁡ n \lg nlgnCase 3根节点强f ( n ) Ω ( n log ⁡ b a ϵ ) f(n) \Omega(n^{\log_b a \epsilon})f(n)Ω(nlogb​aϵ)Θ ( 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 alogb​a算错会导致全盘皆输。例如若误算成log ⁡ 2 4 1 \log_2 4 1log2​41就会得出错误结论。区分n lg ⁡ n n\lg nnlgn和n 2 n^2n2在渐进复杂度中多项式级n x , x 1 n^x, x1nx,x1永远大于线性对数级n lg ⁡ n n\lg nnlgn。