先说明一下我这个“习题2.4”不是凭空编的而是根据算法设计与分析课程里最常见的章节安排来定位的。大部分教材讲到第2章正好是递归与分治策略配套的习题基本都会落在递归式求解、复杂度分析、主定理应用这几个方向上。所以这篇博文里的题目场景、推导思路都是按这类习题的标准套路来展开的你拿到自己的习题2.4思路也是相通的。如果你是正在啃算法课的本科生或者准备考研复试、找工作笔试时想捡起复杂度分析的人这篇内容应该对你有用。我不会堆一堆数学符号就完事而是把每一步推导背后的想法、常见的坑、以及考试和面试里怎么把过程写规范都尽量讲透。1. 习题2.4到底在考什么拆题思路先搞明白1.1 这类习题的共同特征递归式求解第2章的习题2.4十有八九跑不出递归式分析的范畴。所谓递归式就是描述算法运行时间的方程比如T(n) 2T(n/2) n意思是规模为 n 的问题被拆成 2 个规模为 n/2 的子问题合并子问题结果需要 n 的时间。很多同学第一次看到这种式子会懵这不就是个数学公式嘛跟算法有什么关系我来打个比方。把解决一个问题看成你组织一群人搬家。你当队长先把物品按区域分成两堆让两个小组长各带一半人分别处理每个小组长又继续往下分直到每个组员只管一小块。最后你把各组的成果汇总。T(n) 2T(n/2) n 的意思就是你找两个组长各管 n/2 的活儿你自己额外花 n 的时间做分派和汇总。这个递归展开下去就是整个搬家的时间总账。习题2.4通常不会只给一棵简单的递归树就完事它会让比较不同的递归式体会不同合并代价对总复杂度的影响。1.2 解题前先定位这是剖析复杂度不是写代码做这类题最大的误区是拿编程的思路去套。有人一看到 T(n) 2T(n/2) n就想着写个递归函数模拟一下。真没必要也不推荐。算法设计与分析这门课里的习题重点是数学建模能力不是语言功底。你拿到一个递归式要做三件事第一正确展开递归观察每层的规模变化。第二算出每一层总共多少工作量把各层累加起来。第三判别最终结果属于哪个渐近复杂度级别。这就像记账左边记“每层花多少时间”右边记“一共多少层”最后一合计就是总账。所谓“分析习题”本质上就是把这个账算明白。2. 绕不开的前置工具递归树、主定理和代换法2.1 递归树最直观的算账方式递归树是解决递归式最推荐的入门工具。它的思路就是把递归展开过程画成一棵树。比如T(n) 2T(n/2) n根节点是 n表示第一层的合并开销。它有两个孩子每个孩子规模 n/2表示两个子问题的递归调用。每个孩子节点内部再继续往下分。叶子节点是递归基通常是 T(1)。为什么理解这个工具很重要因为后续的所有方法本质上都是在跟递归树对话。主定理是用公式总结了一类树的规律代换法是靠猜结果然后验证但只有递归树能让你亲眼看到复杂度是怎么一层层累积出来的。2.2 主定理一类特殊递归式的直通车主定理是个公式它解决的是形如T(n) aT(n/b) f(n)这类递归式其中 a≥1b1f(n) 是渐近正函数。它的核心思想是比较 f(n) 和 n^(log_b a) 的大小关系谁大听谁的如果一样大就乘个 log n。具体来说分三种情况如果 f(n) 小于 n^(log_b a)即 n^(log_b a) 占主导则 T(n) Θ(n^(log_b a))。如果 f(n) 约等于 n^(log_b a)则 T(n) Θ(n^(log_b a) log n)。如果 f(n) 大于 n^(log_b a)并且满足某个正则条件则 T(n) Θ(f(n))。很多同学在这里容易出问题就是只记住了“谁大听谁的”但忽略了正则条件和多项式意义上的比较。所谓“大于”或“小于”不是差一点点而是相差一个 n^ε 因子这个细节后面我会专门展开。2.3 代换法先猜后证基础要扎实代换法分两步先猜复杂度再用数学归纳法证明。这个方法看起来简单但“猜”得有依据。比如看到 T(n) 2T(n/2) n你可能猜 T(n) O(n log n)然后带入归纳假设去验证。代换法真正难的地方在于归纳证明时要处理低阶项。比如你猜 T(n) ≤ c n log n代入递归式后可能出现一个多余的 n导致结论差一点需要调整常数 c 或者减去一个低阶项才能收尾。这种经验不练几次是体会不到的。这里我个人有个建议递归树和主定理是做题的主力代换法是验证和兜底工具。考试时间充裕时用递归树推导再尝试用代换法验证一遍准确率会高很多。3. 习题2.4完整实操从题目到答案的推演全记录3.1 题目设定与我们的已知条件这里我以一道典型习题为例用递归树方法求递归式 T(n) 2T(n/2) n log n 的渐近复杂度并说明主定理是否适用。这个题目的答案很多参考书会直接给 Θ(n log² n)但过程写得特别简略。我在这里把完整的推演展开。先说明一个关键点这个递归式不满足主定理的情形。如果你直接套主定理a2b2那么 n^(log_2 2) n而 f(n) n log n。f(n) 比 n 大但大到什么程度它只多了一个 log n 因子不是多项式级别的“显著大于”所以主定理的第二、三种情况之间正好有个空档直接套用会错。这正是出题人想考察的细节。3.2 递归树逐层展开与计算画出递归树。根节点规模 n代价 n log n下一层有两个节点每个规模 n/2代价各为 (n/2) log(n/2)。总代价 2 × (n/2) log(n/2) n log(n/2)。再下一层有四个节点每个规模 n/4总代价 4 × (n/4) log(n/4) n log(n/4)。规律已经很清晰了。第 k 层的总代价是n log(n / 2^k)注意这个数列并不是等比数列而是每层都在变化的。因为 log(n/2^k) 会随 k 增大而递减直至到叶子层附近变成 0 附近的常数。递归树的高度是多少从 n 每次除以2直到 1层数 k 的范围是从0到 log₂ n。所以树的高度是 log₂ n。现在把各层代价加总T(n) Σ_{k0}^{log₂ n - 1} n log(n / 2^k)对这个和式做一下化简。log(n / 2^k) log n - k所以T(n) Σ_{k0}^{log₂ n - 1} n (log n - k) n Σ_{k0}^{log₂ n - 1} (log n - k)令 H log₂ n那么上面这个和式就是Σ_{j1}^{H} j H(H1)/2也就是从 1 加到 H。于是T(n) n × O(H²) n × O(log² n) O(n log² n)如果你想确认下界可以用同样的思路构造一个只取前半部分的求和得到 Ω(n log² n)。所以最终结论是 T(n) Θ(n log² n)。3.3 主定理为什么不适用这里讲透前面提到这个递归式里 n^(log_2 2) nf(n) n log n。主定理的三种情况要求 f(n) 和 n^(log_b a) 之间存在多项式级别的差距。也就是说要不 f(n) O(n^(1-ε))要不 f(n) Ω(n^(1ε))。可是 n log n 比 n 大却又没有大到 n^(1ε) 的程度正好卡在中间空白地带三种情况都够不着。这个习题的妙处就在这里它逼着你不能死记公式必须会画递归树或者会用更广义的一些变形方法。很多同学在这道题上扣分不是算错而是没有说明“主定理不适用”这个前提上来就生搬硬套。这也提醒我们任何工具都有适用范围理解工具的边界和掌握工具本身同样重要。3.4 代换法验证完整步骤用代换法来验证 T(n) O(n log² n)顺便练一练归纳证明。假设对规模小于 n 的情况T(m) ≤ c m log² m其中 c 是某个常数。代入递归式T(n) ≤ 2c (n/2) log²(n/2) n log n c n log²(n/2) n log n展开 log²(n/2) (log n - 1)² log² n - 2log n 1于是T(n) ≤ c n log² n - 2c n log n c n n log n c n log² n - (2c - 1) n log n c n只要取 c≥1中间项 (2c-1) n log n 就是正的可以吸收掉后面的 c n。因此T(n) ≤ c n log² n归纳成立所以 T(n) O(n log² n)。这里要用到一个小技巧当归纳证明消不掉多出来的低阶项时可以把假设改成 T(m) ≤ c m log² m - d m然后用调节常数的方式来凑。这种“减一个低阶项”的手法在算法分析里很常见面试手撕题时也经常用到。3.5 完整答案该怎么写才规范考试和作业里光写得数不对过程是要扣分的。我建议按这个结构写第一步画出递归树前两层说明每层规模和总代价。第二步写出第 k 层的通用表达式。第三步确定递归树高度写出各层总代价的求和式。第四步在草稿纸上化简求和得出最终渐近复杂度。第五步简要说明主定理为什么不适用如果题目问到了。这种写法在阅卷时最受用。因为阅卷人想看到的不是跳步的结果而是你清晰展示了“我知道自己在算什么”。4. 作业和考试里最常见的坑现场排错实录4.1 把递归树画成每层代价等比递减结果越算越偏很多同学在看到 T(n) 2T(n/2) n 这种标准题型时学会了每层代价都是 n。于是碰到 T(n) 2T(n/2) n log n 时想当然地以为每层代价都一样最后算出 O(n log n)错了。实际展开后第 k 层代价是 n log(n/2^k)是一个逐渐减小的变化量不是常数。判断每层代价时正确做法是先把第 0 层、第 1 层、第 2 层的具体表达式写出来观察规律后再求和不要凭感觉套。4.2 主定理的适用边界理解错了有的题目把递归式写成 T(n) 2T(n/2) n²这时 f(n) n² 远大于 n所以答案是 Θ(n²)这没问题。但如果是 T(n) 2T(n/2) n log n就掉坑了因为中间地带不属于常规主定理管辖。还有一个常见变体是 T(n) 2T(n/2) n / log nf(n) 比 n 小但小得不够多项式级别同样不满足条件一。这类“只差一个log”的情形是出题人的偏爱在习题2.4里出现概率很高。判断主定理是否可用我建议养成一个习惯除了看 a、b、f(n)还要把 f(n) 和 n^(log_b a) 的比值写出来看看是否相差 n^ε 因子。如果没有就不要硬套。4.3 递归树高度算错整题白做高度是 log_b n但底数到底是多少很多人会搞混。T(n) 2T(n/2) 里 b2高度是 log₂ n。如果 T(n) 3T(n/4)则 b4高度是 log₄ n。高度决定了求和项的个数就算每层代价表达式写对了求和范围写错也会导致结果错误。这里我提供一个自查方法假设 n16递归到 T(1) 时经过几步16→4→1两步正好 log₂ 16 4 减一。通过具体数值代入去验证抽象的层数公式能减少很多笔误。4.4 忽略常数因子导致渐近级别判断失误还有一个常见问题是忽略合并代价里的常数系数。T(n) 2T(n/2) 3n 和 T(n) 2T(n/2) n从渐近分析的角度看都是 Θ(n log n)常数 3 不影响级别这叫主定理对常数不敏感。但有些同学看到 3n 就慌觉得复杂度高了这是没有理解渐近符号的含义。不过要注意如果题目明确要求“精确分析常数因子”那就要格外小心了。这种题通常是为了比较两种算法的实际效率而不是只看理论级别。这时候把常数项写进每层求和里才安全。5. 习题2.4带出来的延伸思考从应付作业到真正理解算法5.1 递归式分析和分治法设计是孪生兄弟写分治算法的代码时划分阶段和合并阶段的复杂度会直接决定整个算法的性能。归并排序的递归式是 T(n) 2T(n/2) n因为合并两个有序数组是线性的快速排序平均情况也是 T(n) 2T(n/2) n。如果你设计了一个分治算法发现合并阶段是 n²那么递归式就变成 T(n) 2T(n/2) n²整体复杂度直接上升到 Θ(n²)分治的优势就没了。所以分析习题的价值不只是做题它是在训练一种敏感度当你设计算法时能提前估算性能而不必等写完代码再跑实验。这种能力在工程里同样有用比如设计数据同步任务时决定是把大任务拆分并行还是串行处理心里先有个复杂度账本会稳很多。5.2 从单道题总结出一类题的通用解法我见过不少同学做习题2.4时一道三道题单独做做完就完。其实更好的做法是按递归式的“合并代价类型”做一个分类对比合并代价是常数T(n) 2T(n/2) 1复杂度 Θ(n)。合并代价是线性T(n) 2T(n/2) n复杂度 Θ(n log n)。合并代价是 n log nT(n) 2T(n/2) n log n复杂度 Θ(n log² n)。合并代价是平方级T(n) 2T(n/2) n²复杂度 Θ(n²)。把这四种放在一起对比能很明显感觉到“瓶颈在哪一层”。常数代价时总代价由叶子节点数决定平方代价时根节点就决定了总复杂度。这种层级的感知才是这门课真正想教的。5.3 考前快速检查清单如果你马上要考算法分析了我建议把这几点写在草稿纸角落递归树高度 log_b n先确认 b。每层代价不要凭感觉写出第0层、第1层、第2层再归纳。主定理只适用于“多项式级别差”的比较碰到 log 因子卡边界时优先递归树。代换法证明别忘了预留常数空间吸收低阶项。最后写答案时务必用 Θ 符号而不是 O除非题目只要求上界。这个清单我每次布置作业前都会反复给学生强调因为踩过太多次重复的坑。6. 常见问题速查表为了方便你们复习我把这类题最典型的几个问题和处理办法整理成一张表问题现象可能原因解决思路套主定理得到 O(n log n)但递归树展开却是 O(n log² n)f(n) 与 n^(log_b a) 之间只差 log 因子属于主定理盲区改用递归树逐层求和递归树画到底高度不确定没有明确递归终止条件先设 T(1)Θ(1)从 n 除以 b 直到1来确定层数代换法归纳到第 k 步差一个 n 项收不掉归纳假设缺低阶项改设 T(n) ≤ c n log n - d n调节 d求和表达式写出来但不会化简对 Σ(log n - k) 不敏感令 Hlog₂ n先做变量代换再求和把 O 和 Θ 混用没有严格证明上下界通常用递归树同时得上下界再写 Θ这张表可以直接当成习题课的复习提纲遇到对应情况翻一下比自己闷头纠结效率高得多。最后再说一点个人感受我当年学算法设计与分析时第一次做递归式求解也觉得绕递归树画着画着就乱了。后来发现只要每一步都老老实实写出“第 k 层代价”并且拿具体 n 值代入核验正确率会大幅提升。这道习题2.4放到多年后再看反而是帮我把分治算法理解透的转折点。如果你也正在被递归式折磨不妨多一些耐心把每个推导步骤写到能说服自己为止。过了这一关后面的分治算法、动态规划、摊还分析都会有更扎实的地基。