先说明一下，我这个“习题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≥1，b>1，f(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)，但过程写得特别简略。我在这里把完整的推演展开。

先说明一个关键点：这个递归式不满足主定理的情形。如果你直接套主定理，a=2，b=2，那么 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) = Σ_{k=0}^{log₂ n - 1} n log(n / 2^k)

对这个和式做一下化简。

log(n / 2^k) = log n - k

所以：

T(n) = Σ_{k=0}^{log₂ n - 1} n (log n - k) = n Σ_{k=0}^{log₂ n - 1} (log n - k)

令 H = log₂ n，那么上面这个和式就是：

Σ_{j=1}^{H} j = H(H+1)/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) = n，f(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 n，f(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) 里 b=2，高度是 log₂ n。如果 T(n) = 3T(n/4)，则 b=4，高度是 log₄ n。高度决定了求和项的个数，就算每层代价表达式写对了，求和范围写错也会导致结果错误。

这里我提供一个自查方法：假设 n=16，递归到 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 n：T(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. 常见问题速查表

为了方便你们复习，我把这类题最典型的几个问题和处理办法整理成一张表：

这张表可以直接当成习题课的复习提纲，遇到对应情况翻一下，比自己闷头纠结效率高得多。

最后再说一点个人感受

我当年学算法设计与分析时，第一次做递归式求解也觉得绕，递归树画着画着就乱了。后来发现，只要每一步都老老实实写出“第 k 层代价”，并且拿具体 n 值代入核验，正确率会大幅提升。这道习题2.4放到多年后再看，反而是帮我把分治算法理解透的转折点。如果你也正在被递归式折磨，不妨多一些耐心，把每个推导步骤写到能说服自己为止。过了这一关，后面的分治算法、动态规划、摊还分析都会有更扎实的地基。