说实话每次翻开《算法设计与分析》的习题册很多同学都会卡在类似习题2.5这种题目上——不是看不懂题目而是不知道从哪下手写分析过程。我当年带这门课助教的时候批改作业发现大家的错误出奇地一致递推式列出来了但解不出来或者递归树画到第三层就放弃再或者干脆凭感觉写一个复杂度上去连自己都说服不了。这道题真正想训练的其实是算法分析里最核心的一套基本功把一个算法的运行时间写成一个数学表达式递推式然后用工具把它解出来最后给出一个干净的渐进界。这套能力在后续的分治法、动态规划、回溯法章节里每一次都会用到。这篇就把习题2.5这类题目的完整分析思路拆开讲透从读题、建递推式、选解法到验证结果每个环节都有可以直接抄的套路。1. 拿到分析题先想清楚这三件事别一上来就盯着代码看。先问自己三个问题这段代码的结构是递归还是迭代如果递归它的递归划分是什么样除了递归调用之外每次调用还额外干了多少私活1.1 习题2.5到底在考什么这类题通常会给一段分治代码让你求时间复杂度的渐进上界和下界。考察点一般落在三个层面第一层是读懂递归结构。代码里递归调用了几个自己每递归一次规模缩小到原来的几分之几比如T(n) 2T(n/2) cn和T(n) T(4n/5) T(n/5) cn表面上都是递归线性合并但前者是等分划分后者是不等分划分解出来一个是 Θ(n log n)一个也是 Θ(n log n) 但推导路径完全不同。第二层是写出正确的递推式。很多人栽在这里忽略了递归基base case的常数代价或者漏掉了每次调用内部循环的开销。正确的递推式必须覆盖递归代价 非递归代价两部分一个都不能少。第三层是选择合适的求解方法。递归树、主定理、代换法各有各的适用场景选错了会绕很大的弯路。1.2 分析问题的标准流程我给自己定的分析流程是四步每一步都有明确的产出物画结构图把递归调用关系画出来搞清楚每次调用自身之后规模怎么变化。写递推式T(n) 递归部分 非递归部分必要时分情况讨论。求解优先看能不能套主定理不能套就画递归树递归树搞不定再用代换法猜。验证把解代回原递推式验证是否成立或者用几个小 n 手动模拟一下看复杂度量级是否合理。这套流程看起来简单但能坚持走完每一步尤其是最后一步验证能避免超过一半的粗心错误。2. 递推关系的建立与求解三件套工具逐一上手递推式的求解方法重点是这三件套递归树、主定理、代换法。下面逐个讲清楚什么情况用哪个、怎么用、容易在哪里翻车。2.1 递归树法可视化每一层开销递归树法的思想特别直观把递归过程展开成一棵树每一层把所有节点的开销相加得到该层总开销最后把所有层的开销加起来就是总复杂度。举个例子T(n) 2T(n/2) cn。画出来就是根节点开销 cn下一层两个节点各开销 c(n/2)总开销还是 cn再下一层四个节点各开销 c(n/4)总开销还是 cn。树高是 log_2 n每层都是 cn总复杂度就是 cn · log_2 n即 Θ(n log n)。递归树法的优势是对不规则的递归也能处理。比如T(n) T(n/3) T(2n/3) cn这棵树左右不等高但可以证明每层开销都≤ cn且树高大约是 log_{3/2} n因此 T(n) O(n log n)。配合一个下界论证最后一层贡献一个常数×n能得出 Θ(n log n)。这种题目用主定理反而束手束脚因为不满足标准形式。2.2 主定理三行代码搞定标准形式主定理Master Theorem适用于形如T(n) aT(n/b) f(n)的递推式其中 a≥1, b1。核心是比较 f(n) 和 n^(log_b a) 谁更大条件结论f(n) O(n^(log_b a - ε))ε0T(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 ε)) 且 a·f(n/b) ≤ c·f(n)c1T(n) Θ(f(n))实际使用中最常见的坑是忽略第三条的条件。有人只看 f(n) 是 Omega 就直接套 Θ(f(n))结果递推式T(n) 2T(n/2) n log n就翻车了因为这里 f(n) n log nn^(log_2 2) nf(n) 严格大于 n 但又不满足 f(n) Ω(n^(1ε))。这种情况递归树比主定理靠谱。2.3 代换法先猜后证的高级技巧代换法分两步先猜一个上界然后用数学归纳法证明。这个方法适合主定理覆盖不了、递归树又不好画的递推式。比如T(n) 2T(√n) log n。先尝试猜 O(log n)。设 T(n) ≤ c·log n代入得 T(n) ≤ 2c·log(√n) log n c·log n log n。这里比 c·log n 多出了一个 log n说明 c 不够大。改设 T(n) ≤ c·log n - d代入得 T(n) ≤ c·log n - d log n。只要选 d ≥ 1 就能成立。这个例子提醒我代换法猜解时要在假设式里预留一个常数项否则很容易被多出来的低阶项卡住。3. 实操环节完整走一遍复杂度分析流程讲完基础工具拿一道习题2.5风格的题目来过一整套流程。原题大概是这样的一个递归算法在每次调用时会执行两层嵌套循环循环次数由当前规模 n 决定然后递归调用自身两次规模折半。让你求时间复杂度的精确渐进界。把题目还原成伪代码就是这个样子void func(int[] arr, int l, int r) { if (l r) return; int m (l r) / 2; for (int i l; i r; i) { for (int j i 1; j r; j) { // 常数时间操作 } } func(arr, l, m); func(arr, m 1, r); }3.1 步骤一写递推式设规模为 n r - l 1。递归部分是两个规模 n/2 的子问题非递归部分是双层循环开销是[ \sum_{il}^{r} \sum_{ji1}^{r} 1 \binom{n}{2} \frac{n(n-1)}{2} ]所以递推式为[ T(n) 2T(n/2) \frac{n(n-1)}{2} ]通常写渐进形式就够用了[ T(n) 2T(n/2) \Theta(n^2) ]3.2 步骤二递归树展开这题的递归树长这样根节点开销 c·n²下一层两个节点每个开销 c·(n/2)² c·n²/4总开销 c·n²/2再下一层四个节点每个开销 c·(n/4)² c·n²/16总开销 c·n²/4。看出来规律没有每层总开销依次是 n²、n²/2、n²/4、n²/8……这是一个等比数列公比是 1/2。这里有同学会下意识觉得每层都是 n²所以总共是 n² log n这是错的。树高虽然是 log n但每层的开销在递减而不是保持不变。精确求和[ T(n) cn^2 \left(1 \frac{1}{2} \frac{1}{4} \cdots \right) cn^2 \cdot 2 ]结果就是 Θ(n²)。3.3 步骤三用主定理验证T(n) 2T(n/2) Θ(n²)。a2, b2, log_b a 1。f(n) n²和 n^1 比较f(n) 明显更大且满足正则条件所以直接落在主定理的第三种情况结论同样是 Θ(n²)。两种方法殊途同归。但注意一个细节如果合并开销是 Θ(n²)这棵树的总开销主要由第一层决定后面的层贡献越来越小。所以结论可以这么理解合并开销是平方级的递归算法即使递归了 log n 层总复杂度依然由第一层主导。3.4 步骤四复杂度量级验证为了让自己放心可以取几个具体值验证。令 n8递归树第一层开销 64c第二层两个 16c32c第三层四个 4c16c共 112c。如果用 Θ(n²)估计大约是64c倍数实际112c在小常数范围内量级判断没问题。这道题的关键收获是递归层数不直接等于复杂度倍数要看每层开销是否递减、持平还是递增。分三类归纳一下每层持平→乘以log n每层递增→通常由叶层主导复杂度翻倍式增长每层递减→由根层主导复杂度就是第一层的量级。如果每层递增这类题的答案往往是 Θ(2^(log_b a · log_2 n)) 这种形式。把这三类记牢绝大多数分治复杂度题都能快速定性。4. 做题时最容易翻车的4个细节细节决定习题能不能拿满分。以下这4个坑我在批改作业和面试刷题时反复见到逐一说透。4.1 忽略递归基的开销很多教科书版本的递推式会写成T(1) O(1)这不代表递归基可以随意处理。当 n 比较小时递归基的执行次数可能达到 Θ(n) 量级忽略它会低估复杂度。比如T(n) T(n/2) 1解出 T(n) Θ(log n)。但如果你把T(1)0错误地当成常数省略推导过程中就会发现最后结论对不上。写递推式时T(1) O(1)必须写明不要省略。4.2 合并开销的常数不是摆设常数时间也有系数在渐进分析中系数可以忽略但在写递推式的阶段这个系数必须保留否则可能影响对递归树层间开销趋势的判断。举个例子T(n) 2T(n/2) n/2和T(n) 2T(n/2) 2n的合并开销分别是 0.5n 和 2n两者都是 Θ(n)最终解也都是 Θ(n log n)。但如果系数是接近0呢比如 n/1000虽然渐进上不影响但这道题如果要求精确到常数系数就不能一上来就写成 Θ(n)。4.3 混淆最好、最坏与平均情况某些算法比如快速排序最好/最坏/平均复杂度分别是 Θ(n log n)、Θ(n²)、Θ(n log n)。习题给出的伪代码可能默认是平均情况也可能要求分析最坏情况。拿到题先确认题目问的是哪一个。如果没说通常默认最坏情况因为最坏情况分析不依赖概率分布数学上更严格。但有些教材的习题会故意写假设每次划分恰好把数组分成两半这就是在暗示你走平均或理想情况的路线。4.4 主定理第二条边界别硬套主定理第二条要求 f(n) Θ(n^(log_b a))。实际题目中出现 f(n) cn^k (log n)^p 这种形式时需要对第二条做推广[ T(n) \Theta(n^k \log^{p1} n) \quad \text{若} \quad f(n) n^k (\log n)^p ]但前提是 k log_b a。如果 k 略小或略大就不能直接套第二条。很多人背结论只背了三行遇到推广形式就乱套。建议遇到混合多项式先画递归树反而更稳。5. 从作业题到面试题算法分析能力怎么迁移习题2.5虽然只是一道课后题但它背后训练的分析能力直接对应着面试里的大题和真实项目中优化算法的思路。很多刷题平台上的 hard 题本质都是递归结构 合并开销的组合分析。5.1 面试中经典的复杂度反问面试官最喜欢问的一个问题是你这个解法的时间复杂度是多少如果你只答一个O(n log n)面试官大概率会追问为什么是 n log n递归树每一层开销一样吗能清楚回答这个问题的人和只背了答案的人差距就在是否真正理解了递归树的层间开销模式。我在面试中遇到过一个候选人写了一个二维分治算法复杂度写了个 O(n² log n)。我让他画递归树他画到第二层就发现每层开销是递减的最后自己纠正成了 O(n²)。这种发现并修正的过程比直接答对更能展现算法功底。5.2 实际项目里的复杂度眼光真实业务代码很少有教科书式的分治结构但复杂度的分析方法无处不在。举一个真实例子一个日志处理程序每天的数据量大得压垮内存于是把任务按小时切分分给多个进程处理最后合并结果。如果合并过程需要把每小时的索引都扫一遍合并开销就是 O(n × 分片数)整体复杂度就要重新评估。这时候能画出递归树其实是任务树并判断哪一层开销主导决定了系统能不能撑住数据增长。很多系统慢不是因为某个算法选错了而是因为对开销分配没有量化的直觉——不知道瓶颈究竟在第一层合并还是最后一步汇总还是整个过程的每一层。5.3 把习题里的方法论抽象成通用模板做完习题2.5我建议你把分析过程抽象成一个模板之后遇到任何递归算法都往里面套递归划分a 个子问题规模缩小为 n/b用 T(n) aT(n/b) 表示。非递归开销找出每次调用中独立于递归的开销函数 f(n)。层间模式算第一层 f(n)第二层 a·f(n/b)第三层 a²·f(n/b²)看趋势。求总和等比求和或者套主定理或者代换法。验证代入一个具体 n手动模拟几层确保结论不荒谬。这套模板熟练之后看到任何分治代码十秒内能口算出复杂度。我自己带实习生时要求他们先背模板再做习题正确率提升非常明显。最后再分享一个小技巧如果你在化简递归树求和时卡住了把每层的开销写成分数形式不要用小数然后看有没有约分的可能。很多看似复杂的求和约分完就是一个等比数列或者调和级数。比如 n² n²/2 n²/4 ... 约分后就是标准的 1 1/2 1/4 ... 2。我在给研究生改论文的时候发现不少人卡在中间纯粹是因为用小数把规律写没了。保持分数的形式复杂度求和的速度会快很多也更容易看出层间是递增、递减还是持平。
