不管你是正在啃《算法设计与分析》教材的大二学生还是马上要考算法课、刷笔试面试题的应届生第二章的习题 2.2 大概率是你遇到的第一个“坎”。我当年第一次翻开这本书的第二章时心态是比较放松的——毕竟第一章的复杂度概念也就是背背 Big-O、Omega、Theta 的定义。但等我看到习题 2.2 的时候发现事情没那么简单递归方程、分治策略、递推展开、主定理一股脑全塞过来了。这节课的习题如果只靠“看一遍课本例题”来应对基本上一做就废。这篇文章我想用过来人的口吻把习题 2.2 背后真正要考察的东西拆给你看——它到底在考什么、有哪些固定的解题套路、写答案的时候怎么一步步推导不容易丢分以及我自己踩过的一些坑。不管你的教材是常用的那几本经典教材里的哪个版本习题编号可能略有差异但第二章对应“递归与分治”这个主线是非常固定的习题 2.2 通常就是围绕递归方程求解和分治复杂度分析出题。理解清楚这部分后面学动态规划、贪心算法、回溯法都会轻松很多。1. 习题 2.2 背后的知识主线递归方程与分治策略1.1 为什么第二章的习题总离不开递归方程算法设计与分析这门课第二章的知识主线基本可以概括为两个词递归、分治。分治策略说起来简单——把一个规模为 n 的问题拆成若干个规模更小的子问题分别求解后再合并结果。但真正做题的时候你不可能只在文字层面理解“拆、解、合”这三个字你需要用一个数学工具把这种“拆分-递归-合并”的过程表达出来这个工具就是递归方程也叫递推方程。递归方程的长相很典型它描述的是T(n) 与若干个更小规模上 T 的关系。比如二分搜索对应的递归方程是 T(n) T(n/2) O(1)意思是解决规模为 n 的问题要先解决一个规模为 n/2 的子问题再加上一次比较的开销。冒泡排序优化的分治版本、归并排序对应的则是 T(n) 2T(n/2) O(n)每次都要递归解决两个大小为 n/2 的子问题合并时还要花 O(n) 的时间。习题 2.2 之所以成为经典习题是因为它把所有“看起来很简单但算起来容易乱”的东西集中到了一起。你会发现光会列递归方程不够还得会解。所谓“解”就是把这个递归方程变成我们熟悉的闭式形式比如 T(n) O(n log n)这样才能回答“这个算法到底快不快”的问题。1.2 同一个习题为什么要掌握三种解法解递归方程的常用方法有三种代入法代换法、迭代展开法递归树法、主定理法Master Theorem。很多教材把主定理放在后面的章节而习题 2.2 作为“第二章的习题”可能会要求你不使用主定理靠展开和代入来推导。这其实是一种很好的训练它逼着你真正理解递归方程在说什么而不是背一个公式套用。我在实际带人复习时经常遇到这种情况学主定理之前大家觉得迭代展开法太笨、太麻烦学了主定理之后又觉得前面两种方法完全多余。但真到考试和面试里你往往没有现成的定理可用——面试官可能当场给你一个形如 T(n) 3T(n/2) O(n^2) 的方程让你算复杂度你能用主定理当然快但如果这个方程不满足主定理的条件比如子问题规模不是精确等分或者代价函数不是多项式量级你就必须用别的办法。所以我这篇博文里会把三种解法都讲一遍并给出我自己的判断什么时候优先用什么方法哪些题型用哪种方法最不容易错。下面先拆题型。2. 题目类型拆解与解题模板2.1 题型一直接给算法描述要求列出递归方程并求解这类题是习题 2.2 里最常见的。题目给你一小段伪代码比如一个二分查找的递归实现或者一个分治求最大最小值的算法要求你写出它的递归方程再分析时间复杂度。先看怎么列递归方程。列方程的核心是搞清楚两个问题递归子问题的规模是多少除了递归调用之外每次调用还要做多少额外工作以二分查找为例伪代码可能是def binary_search(arr, target, low, high): if low high: return -1 mid (low high) // 2 if arr[mid] target: return mid elif arr[mid] target: return binary_search(arr, target, low, mid - 1) else: return binary_search(arr, target, mid 1, high)每次调用只进入其中一个递归分支所以子问题规模是 n/2额外比较是 O(1)。递归方程为 T(n) T(n/2) O(1)边界条件是 T(1) O(1)。再看分治求数组最大值的算法def find_max(arr, low, high): if low high: return arr[low] mid (low high) // 2 left_max find_max(arr, low, mid) right_max find_max(arr, mid 1, high) return max(left_max, right_max)这里递归会产生两个子问题每个规模 n/2合并操作 max 是 O(1)。所以方程是 T(n) 2T(n/2) O(1)解得 T(n) O(n)。注意这个算法虽然是分治结构但它并不比简单的线性扫描更快因为每个元素还是被访问了一次。2.2 题型二直接给递推方程要求求出渐进复杂度第二种题型则省去算法描述直接甩给你一个递推式比如 T(n) 3T(n/2) n^2然后问 T(n) 的渐近上界。这类题考验的就是纯粹的解方程能力。我的经验是拿到这种题以后先别急着套主定理先用几秒钟做个判断方程里 n 前的系数是 1 还是大于 1大于 1 意味着有多个子问题解出来通常是指数级或 n 的多项式乘以对数因子。额外项 f(n) 是 n^k 形式还是包含 log n这决定了递归树每一层的总代价是增长还是不增长。有没有出现 T(n - c) 而不是 T(n / c)一旦是这种“减常数”的递推主定理不能直接用通常得靠展开。判断完这些之后再选择合适的方法。这种“先判断、再动手”的习惯才是习题 2.2 真正想教给你的。2.3 题型三给定算法功能描述要求自己设计递归式并说明复杂度第三种题型在笔试里很常见题目问你设计一个分治算法找一个数组里第 k 小的元素然后分析它的时间复杂度。这时候你需要先写出算法思想再给出递归方程再分析复杂度。这种题目对理解深度的要求更高。因为它不光是“解方程”还要求你先会“列方程”。综合来看习题 2.2 的三个题型占据了算法笔试的大部分复杂度分析场景。下面的章节我直接给你展示三道完整例题的推导过程你可以把这些推导当成模板考试时照着这个格式写。3. 实操演练三道典型习题 2.2 的完整推导3.1 例题一T(n) 2T(n/2) n 的迭代展开与递归树第一道题是几乎所有教材都会出现的归并排序复杂度推导T(n) 2T(n/2) nT(1) O(1)。我用迭代展开法来做。核心思路是把一个关于 T(n) 的等式反复套用直到可以用 T(1) 替换。第一层展开T(n) 2T(n/2) nT(n/2) 2T(n/4) n/2代入得到T(n) 2 * [2T(n/4) n/2] n 4T(n/4) 2n继续展开 T(n/4) 2T(n/8) n/4T(n) 4 * [2T(n/8) n/4] 2n 8T(n/8) 3n你可以看到规律展开 k 次之后T(n) 2^k * T(n/2^k) k * n。问题是什么时候停下来当 n/2^k 下降到 1 时也就是 k log2(n)。代入得T(n) n * T(1) n * log2(n)忽略常数和低阶项T(n) O(n log n)。用递归树的视角看这个过程会更直观。根节点代表规模为 n 的代价 n第二层有两个节点各代表 n/2 的代价 n/2所以第二层总代价是 n第三层有四个节点各代表 n/4总代价还是 n。递归树每一层的工作量都是 n一共有 log n 层总工作量就是 n log n。3.2 例题二T(n) T(n - 1) O(n) 的“减法型”递推习题 2.2 里经常加一道陷阱题用来区分哪些人只会套模板。典型的就是 T(n) T(n - 1) nT(1) O(1)。这对应着类似选择排序里每轮扫描找最小值的时间开销。这里主定理完全帮不上忙因为子问题规模是 n-1 而不是 n/2。你只能老老实实展开T(n) T(n - 1) nT(n - 1) T(n - 2) (n - 1)T(n - 2) T(n - 3) (n - 2)一路展开到 T(1)把所有右边额外项累加T(n) T(1) [n (n - 1) (n - 2) ... 2]括号里面是一个等差数列之和等于 n(n1)/2 - 1约等于 n^2/2。所以 T(n) O(n^2)。我当年在考卷上写这道题的时候犯过一个很蠢的错误我尝试用主定理去套以为 f(n)n 与某个对数因子比较。结果当然算不出来。所以看到括号里是减号、不是除号第一反应应该是“展开求和”而不是背主定理。3.3 例题三Hanoi 塔问题的递归方程 T(n) 2T(n - 1) 1汉诺塔是习题 2.2 的常客。它的递归逻辑是要把 n 个盘子从 A 移到 C需要先把 n-1 个盘子从 A 移到 B再把最大的盘子从 A 移到 C最后把 n-1 个盘子从 B 移到 C。移动一次最大盘耗时 1于是递归方程为T(n) 2T(n - 1) 1T(1) 1展开T(n) 2[2T(n - 2) 1] 1 4T(n - 2) 2 1继续展开 8T(n - 3) 4 2 1展开 k 次T(n) 2^k * T(n - k) (2^k - 1)当 n - k 1 时k n - 1代入T(n) 2^(n-1) * 1 (2^(n-1) - 1) 2^n - 1所以汉诺塔的时间复杂度是 O(2^n)。这个结果很经典也是递归算法未必“高效”的最好例子。很多人会惊讶递归代码看起来那么短为什么算出来是指数复杂度因为递归树里的调用次数本身就是指数级的代码短不等于运行快。我在准备这块内容时额外补充了一个验证方法手动模拟 n3 的汉诺塔。T(3) 2^3 - 1 7意思是三个盘子最少要移动 7 次。你拿三本书自己摆一下就能验证这也是一种很好的自查手段。3.4 主定理用法与一个典型反例如果你学到后面章节用到主定理肯定觉得上面这些推导太原始。但主定理也有自己的适用范围。这里我顺手整理一下最常见的主定理形式对于 T(n) aT(n/b) f(n)其中 a 1b 1f(n) 是渐近正的函数若存在 epsilon 0使得 f(n) O(n^(log_b a - epsilon))则 T(n) Theta(n^(log_b a))。若 f(n) Theta(n^(log_b a))则 T(n) Theta(n^(log_b a) log n)。若存在 epsilon 0使得 f(n) Omega(n^(log_b a epsilon))且对某个常数 c 1 满足 a f(n/b) c f(n)则 T(n) Theta(f(n))。用归并排序举例a2b2log_b a 1f(n) n。因为 f(n) n n^(log_2 2)恰好命中第二种情况所以 T(n) Theta(n log n)。但主定理有个致命的限制f(n) 必须是多项式量级可比较的。比如 T(n) 2T(n/2) n/log n这里的 f(n) 虽然接近 n但它不是多项式级别的 n^(1 ± epsilon)所以主定理的第二种情况严格说并不适用需要借助递归树或者更精细的分析。习题 2.2 里如果出现这类偏题核心目的是让你不要无脑套定理。解法适用场景典型形式输出形式迭代展开任何递推式尤其是减法型T(n) T(n-1) n闭式解递归树分治型递推需要形象理解每层代价T(n) 2T(n/2) n每层代价求和代入法先猜后证适合证明特定上界T(n) c n log n归纳证明主定理标准分治型且 f(n) 满足多项式可比T(n) aT(n/b) n^k直接给出渐近界4. 常见错误与排查技巧4.1 忽略边界条件或用了错误的边界条件我批改过一些同学的作业最常见的问题是展开递归方程时不写清楚递归的“底”。比如展开到 1 的时候边界值应该是 T(1) O(1)但有些人拿 n/2^k 2 停止然后得出了一个多一项少一项的错误结果。收敛条件要细心。以 T(n) 2T(n/2) n 为例n/2^k 1 时得到 k log n如果你把停止条件写成 n/2^k 1k 多取 1最后结果里会多一个常数项渐进分析倒无所谓但你要是求精确表达式就会错。考试的时候大可不必算精确表达式统一用渐近符号更好。4.2 把 T(n/2) 误写成 T((n-1)/2)或者反过来在推导二分搜索时如果数组长度不是 2 的整数次幂严谨地写 T(n) T(ceil(n/2)) O(1) 或者 T(n) T(floor(n/2)) O(1)。做题为了简洁通常会直接写 T(n/2)这是允许的因为取整最多只影响常数因子不影响渐近复杂度。但我见有人在这里卡住他们纠结“如果 n 是奇数那子问题到底是 n/2 还是 n/2 1”我的建议是习题阶段大胆忽略取整只要你会调整边界条件最后结论不变。很多算法教材在推导时也默认 n 是 2 的幂因为这是为了数学上的整洁实际工程代码取整即可。4.3 递归树每层代价计算错误递归树的错误通常会发生在“合并代价”上。举个例子T(n) 3T(n/2) n^2。第一层代价是 n^2第二层有 3 个节点每个代价是 (n/2)^2 n^2/4所以第二层总代价是 3n^2/4。第三层是 9 个节点每个代价是 n^2/16总代价是 9n^2/16。它是一个等比数列公比是 3/4。我第一次算这个的时候会把第二层总代价想成 3 * n^2 / 2然后整体算出一个错误的结果。正确思路是只要递归树每层总代价构成等比数列且公比小于 1那么这个树的总代价会被最大项也就是第一项的常数倍控制属于“根节点主导”的情况。为了让你看清整个过程我用表格把前三层的代价列出来层号节点数每个节点代价本层总代价01n^2n^213(n/2)^23/4 n^229(n/4)^29/16 n^2每一层的总代价都在乘以 3/4所以整体几何级数收敛T(n) Theta(n^2)。4.4 先猜后证时归纳假设强度不够代入法先猜后证也是习题 2.2 常用的方法但我发现很多人败在“猜得太松”。例如你猜 T(n) c n试图证明 T(n) 2T(n/2) n 2 * c * (n/2) n c n n这明显大于 c n不成立。这时候不是急着放弃而是要降低猜测的阶或者加强归纳假设——比如猜 T(n) c n - d其中 d 是某个常数。代入后T(n) 2[c(n/2) - d] n c n - 2d n只要取 d 足够大就能保证 c n - 2d n c n - d也就是 n d。这要求 n 足够小的时候另外验证边界再把常数取大些。这就是“加强归纳假设”的技巧猜 T(n) c n - d而不是简单猜 c n。这一步是我当年最容易忽略的操作。明明归纳法的框架都对但就是差一点点最后发现是下界余量不够需要留出一个“空余量”来吸收推导过程中出现的残差项。5. 从习题到实战分治复杂度分析在工程中的应用5.1 学会用分治思想理解数据处理算法习题 2.2 看起来就是数学推导题但其实它是算法设计的第一个“分水岭”。工程里很多你天天见的数据结构本质都是分治策略的体现。归并排序不用说了快速排序的期望复杂度分析也依赖递归方程。求数组的逆序对、求解平面最近点对问题、用归并思想做外部排序都是第二章习题的推广。我自己在写大数据量下的排序模块时最常用的就是归并排序因为它是稳定排序还能开多线程并行处理各个子段。这时候我脑子里会自动跑一遍递归树每个线程处理 n/2 规模的子问题合并是 O(mn)整体还是 O(n log n)。没有习题 2.2 的反复训练你很难对这种复杂度产生直觉很容易在设计系统时选错方案。5.2 利用主定理的直觉做技术选型做技术选型时我习惯把问题规模、子问题数量、合并代价三件套列出来然后快速判断整体复杂度。比如二分搜索a1b2f(n)1log_b a 0f(n) 与 n^0 同阶所以 O(log n)。归并排序a2b2f(n)nO(n log n)。暴力穷举a2^n这里不是分治了是指数级递归复杂度很高。主定理对我来说是一个“精神上的脚手架”。它让我在写代码之前先从理论上判断一个思路是否可行。如果某个分治算法算出来是 O(n^2)而题目要求 O(n log n)那就得赶紧换方案不要傻傻把代码写完再去优化。5.3 经典面试题的递归方程速查最后整理一个面试笔试里常见的递归方程对照表方便你刷题时快速参考算法场景递归方程渐进复杂度二分搜索T(n) T(n/2) O(1)O(log n)归并排序T(n) 2T(n/2) O(n)O(n log n)找最大/最小值分治T(n) 2T(n/2) O(1)O(n)大整数乘法T(n) 3T(n/2) O(n)O(n^1.585)矩阵乘法StrassenT(n) 7T(n/2) O(n^2)O(n^2.807)汉诺塔T(n) 2T(n - 1) 1O(2^n)选择排序T(n) T(n - 1) O(n)O(n^2)6. 我的实操体会与考试技巧习题 2.2 学完之后我自己总结了一套做此类题目的固定动作分享给你第一永远先写递归方程再写求解过程。很多人喜欢直接来一句“显然复杂度是 O(n log n)”这在考试里是拿不到步骤分的。你要把 T(n) 写出来让它以“数学表达式”的形式出现在试卷上。第二求解时先判断是“除法型递推”还是“减法型递推”。除法型优先考虑主定理减法型基本只能展开。至于混合型比如 T(n) T(n/2) T(n/4) n主定理不方便直接套我会改用递归树估算或者猜一个 n 的上界然后用代入法验证。第三写完推导后代入一个小的 n 做一个 sanity check。比如你算出汉诺塔是 2^n - 1那就拿 n3 验证是 7 步你算出分治找最大值的复杂度是 O(n)那就想象 n8 时递归树有 8 个叶子每个叶子 O(1)总共 O(8)。我在最初学习的时候这个检查习惯帮我抓出不少粗心算错的推导。最后想说一点自己的体会学习算法设计与分析尤其是第二章递归与分治时不要光背公式和定理一定要亲手把一个递归方程从第一层展开到最后一层感受一下那个“树形结构”是怎么生长出来的。你展开过三次理解就完全不一样了。后面学到动态规划的状态转移方程、分治法的许多变体你会发现它们的内核都藏在习题 2.2 这种看似普通的递归方程里。