分治算法习题精讲：递归分析与复杂度推导实战

学过《算法设计与分析》这门课的人大概都有一个共同的体验课后习题看着不难真动笔做的时候却处处卡壳。尤其是第2章的习题恰好卡在“从暴力思维转向分治思维”的坎上很多人在这一章第一次感受到“算法题不是编程题”这句话的分量。习题2.4作为这一章的经典代表背后涉及的递归分析、复杂度推导、边界条件处理几乎覆盖了后续所有算法分析会用到的核心技能。这篇内容我打算不按标准答案的路子讲而是把这道题当成一个切片聊聊怎么读题、怎么建模、怎么验算以及那些老师上课不会明说但考试一定会考的细节。适合看这篇内容的人我建议是正在学算法课程的学生、准备考研复试笔试的考生还有那些刷题多年但始终觉得“复杂度分析只是套公式”的开发者。如果你已经能把二分查找的递归式随手写出来那可以直接跳到第3节看分治推导的完整过程如果你看到递推式就头疼建议从头读我会尽量把每一步拆到不能再拆。1. 先把“习题2.4”放进课程坐标系里1.1 为什么第2章的习题总让人头疼几乎所有算法教材的第2章都围绕“分治策略”展开习题2.4放在这一章的位置相当微妙。往前看第1章刚讲完算法复杂度的基本概念大O、大Theta这些记号刚开始进入视野往后看第3章就要进入动态规划和贪心算法。习题2.4恰好承担了一个承上启下的作用它让你第一次用严谨的数学工具去分析一个非平凡的递归过程。我见过太多学生在做这道题时的状态能说出“分治就是分而治之”这句话但拿到具体题目后既不知道该分几路也不知道合并步骤的成本怎么算。这其实不是理解力的问题而是缺少一个系统化的分析框架。习题2.4的价值就在于此它逼着你把三个问题想清楚第一子问题与原问题是什么关系第二子问题之间怎么组合第三递归的出口在哪里。1.2 教材里习题2.4最常见的三种“长相”不同版本的教材习题2.4的具体题目会有差异但归纳起来逃不出三类。第一类是“递推式求解”比如给定T(n)2T(n/2)cn要求用展开法或主定理求出渐近复杂度第二类是“分治算法设计”比如用分治法在数组中同时找最大值和最小值要你给出算法并分析比较次数第三类是“递归过程分析”比如给一段递归程序要求画出递归树并推导运行时间。接下来的内容我会以第二类“同时求最大值和最小值”作为主线来拆解。倒不是说它比其他两类更高级而是它最能体现分治思想的完整流程——从直觉方案到分治方案从复杂度递推到最优性证明一条线走下来几乎所有核心知识点都能被串起来。而且这道题还有个特别好的地方它的最优方案比较次数是3n/2-2这个常数系数不是凭空来的每一步推导都经得起推敲特别适合用来训练分析肌肉。2. 解一道算法习题真正的起点是“读题”2.1 把题目翻译成算法问题的能力你可能觉得读题谁不会但实操里大部分人栽就栽在“以为自己读懂了”。习题2.4这类分治题题目描述通常只有一两句话但信息密度极高。以同时找最大最小值这道题来说原文多半长这样“设计一个算法从n个元素的数组中同时找出最大值和最小值要求比较次数尽可能少。”这句话里藏着几个关键约束。“同时找出”意味着你不能先找最大值再找最小值因为那样做会重复比较“尽可能少”则暗示存在某种下界你的方案需要尽量逼近这个下界。把这些约束翻译成算法设计目标就变成了我要设计一个比较次数尽量少的算法这个“尽量少”不是拍脑袋决定的而是有理论下界支撑的。我常和学生说读题阶段要养成一个习惯把题目里的每个限定词圈出来然后问自己“如果去掉这个词问题会变成什么样”。比如这里如果把“同时”去掉那顺序扫描两遍就完事了比较次数是2n-2正因为有“同时”我们才被迫去寻找更精巧的结构。这种翻译能力不是天生的练多了之后看到一道题你会自动在脑子里给它打标签这题考的是比较数下界那题考的是空间换时间。2.2 三步拆解法输入、输出、代价我自己做算法题有一个固定的拆解流程分享出来你可以直接拿去用。第一步明确输入形态。这道题的输入是长度为n的数组元素之间可以比较大小没有排序元素可能有重复。第二步明确输出形态。输出是两个值一个是最大值一个是最小值注意不是返回下标而是返回值本身。第三步也是最重要的一步明确你衡量算法优劣的代价指标——这里不是时间复杂度而是“比较次数”因为在这个问题里比较运算是唯一有意义的操作其他语句的成本都是常数量级。这个“把代价指标写清楚”的步骤看着简单但非常值得认真对待。很多初学者做复杂度分析时习惯性地写“时间复杂度O(n)”但在这个问题里你必须精确到系数因为题目要的是“尽可能少”。当系数能被精确计算时O(n)这种粗糙的表达就不够了。理解了这一点你才算真正抓住这类题的精髓复杂度分析不是背公式套符号而是要回到问题的物理本质问自己“每一步操作到底消耗了什么”。3. 手把手拆解分治求最值的完整推导3.1 朴素方案先想清楚最笨的办法在跳进分治解法之前先花点时间把朴素方案掰开揉碎这是很多参考书不会告诉你的事——不理解最笨的办法你根本体会不到聪明方案好在哪里。最直接的办法当然是扫描两遍第一遍从头到尾扫维护当前最大值第二遍再从头到尾扫维护当前最小值。第一遍扫描需要n-1次比较因为每来一个新元素就和当前最大值比一次第二遍扫描同样需要n-1次比较。总共是2n-2次比较。这个数字先记着它是我们的“基准线”。朴素方案的时间复杂度是O(n)看起来已经是线性了似乎没什么可优化的了。但题目要求的是“尽可能少”所以我们必须追问一句2n-2真的是最少的吗直觉上第一遍扫描时有些元素在比较过程中已经暴露了“我不可能是最大值”或“我不可能是最小值”的信息但这些信息在第二遍扫描时完全被浪费了。这个浪费点就是优化的突破口。另外一个值得注意的细节是朴素方案虽然简单但它不需要额外空间原地完成这点在工程上其实很有意义。只是在这个习题场景里我们追求的是最小化比较次数所以需要另辟蹊径。3.2 分治方案两两分组信息复用分治方案的核心思路是成对处理。先把数组里的n个元素两两分组如果n是奇数最后一个元素单独剩下来然后对每一组内部进行一次比较分出较大者和较小者。这一步每组花1次比较一共花了n/2或(n-1)/2次比较。比较结果不要丢掉把这一组的较大者归入“候选最大值集合”较小者归入“候选最小值集合”。接下来的关键操作是最大值只需要在“候选最大值集合”里找最小值只需要在“候选最小值集合”里找。因为每一组的较大者天然不可能是全局最小值每一组的较小者天然不可能是全局最大值。这样一来待比较的范围直接缩小了一半。在候选集合里找最大值需要n/2-1次比较找最小值也需要n/2-1次比较。合计总次数是分组比较n/2次加上两个候选集合内的扫描各n/2-1次总数为3n/2-2次。我强烈建议你拿出纸笔拿一个n8的数组实际走一遍流程。比如数组是[3, 7, 1, 9, 4, 2, 8, 6]两两分组(3,7)比出7和3(1,9)比出9和1(4,2)比出4和2(8,6)比出8和6。候选最大值集合是[7,9,4,8]在这个集合里扫描出最大值9需要3次比较候选最小值集合是[3,1,2,6]扫描出最小值1需要3次比较。总比较次数是43310次而3n/2-212-210完全吻合。对比朴素方案的2n-214次节省了4次。n越大这个节省越明显。3.3 递推式的建立与求解用递归视角重新表述这个分治过程可以得到递推式。把规模为n的问题拆成两个规模为n/2的子问题分别求出每个子问题的最大最小值这一步的代价是2T(n/2)T代表解决子问题所需的比较次数。然后用两次比较把两个子问题的最大值比较出全局最大值把两个子问题的最小值比较出全局最小值。于是递推式写为T(n)2T(n/2)2边界条件是T(2)1两个元素直接比一次就能同时确定最大和最小值。用展开法求解这个递推式T(n)2T(n/2)24T(n/4)428T(n/8)842逐层展开第k层的形式是2^k·T(n/2^k)2(2^k-1)。当n/2^k2时klog2(n/2)。代入整理后得到T(n)n/2·12(n/2-1)3n/2-2。这个结果和前面分步计算的结果完全一致两条路径互相印证答案可信度就非常高了。到这里细心的你可能会注意到这个递推式和归并排序的递推式T(n)2T(n/2)cn形式上很像但常数项的含义完全不同。归并排序的常数项来自合并阶段需要线性扫描而这里的常数项只是2次比较。这个差异直接导致了复杂度系数上的差别。理解递推式中每一项对应算法的哪个步骤是分析能力升级的关键标志不然你永远只是在机械地套展开法。3.4 扩展到一般分治题的分析习惯从习题2.4延伸开去你要建立的一个核心习惯是拿到任何分治算法先写递推式再画递归树再用主定理交叉验证。这三个步骤缺一不可。递推式帮你建立数学直觉递归树让你看到每一层的代价分布主定理则给你一个快速判断的骨架。以本题为例a2b2f(n)2log_b(a)1f(n)O(n^0)因为01所以属于主定理的第一种情况T(n)Theta(n)。和精确结果3n/2-2也不矛盾因为Theta只关心渐近量级不关心常数系数。这里我还想多说一句考试和面试里很多时候只要求说出渐近复杂度但如果你能顺手写出精确的比较次数3n/2-2这个细节会成为明显的加分项。它向别人传递的信号是“我不光会用主定理我还真的理解这个算法的每一分代价”。在算法设计这个领域这种“多走一步”的习惯差距就是在这些地方拉开的。4. 常见错误与排查技巧实录4.1 错误一分治边界条件一错全盘皆输边界条件处理是这道题最大的坑没有之一。新手最常犯的错误是把T(2)1写成T(1)0或T(2)2。T(1)确实不需要比较就能得到“一个元素既是最大值也是最小值”但如果你用T(1)0作为边界展开式会变得奇怪T(2)2则是错误地认为两个元素需要比两次实际上一次比较就能同时确定谁大谁小。这个问题的本质在于递归出口的设定必须和你递推式的定义方式自洽。如果你的定义是“解决规模为m的问题需要的比较次数”那么T(2)的值必须由真实操作决定——两个元素比一次得到较大和较小仅此而已。我建议你在纸上手推展开式时每展开一层就停下来验证当前规模下“剩下几个元素”和“已经花了多少次比较”是否对得上。这种朴素的自检方式比任何高级技巧都可靠。4.2 错误二复杂度符号混用系数说丢就丢另一个高发错误是在写复杂度结论时混淆精确次数和渐近复杂度。有人算出3n/2-2之后大笔一挥写成O(n)这本身没错但如果是在回答“比较次数为多少”的题目写O(n)就是答非所问。记住O(n)表示增长速率的上界3n/2-2才是精确的比较次数。二者的关系就像“月薪过万”和“月薪15000”的区别一个是范围描述一个是精确值面试或考试时后者更有说服力。还有一个常见问题是有些同学在推导过程中把2n-2当成“比较次数下界”得出“不可能再少了”的结论这是明显错误的。2n-2只是朴素方案的次数不是理论下界。要证明3n/2-2是最优的需要用对手论证每次比较最多只能消除一个元素成为最大值或成为最小值的可能性n个元素中排除出最大值候选需要n-1次排除出最小值候选也需要n-1次但一次比较可以同时向两个方向提供信息所以下界是3n/2-2。这个证明思路如果展开写还能独立成一篇短文这里先埋个伏笔后面第5节我会再展开一下。4.3 错误三把“分治”写成“伪分治”还有一种情况值得单独拎出来说。有些人写出来的代码名字叫分治实际运行逻辑却完全没有分治的影子。最典型的伪分治长这样递归函数只调用了一次自身然后扫描整个数组找最大最小值这样递归树的高度虽然是log n但每一层都做线性扫描总代价依然是O(n)且比较次数还是2n-2等于换了个马甲做朴素方案。怎么识别伪分治看递归调用次数。真正的分治必然会把原问题拆成至少两个子问题因为如果只拆成一个那叫减治decrease and conquer虽然一类重要的算法设计方法但在这个题目场景下不会带来比较次数的优化。判断方法是算一下递推式里的a如果a1那就是减治或者伪分治如果a2或者更大才说明你确实把工作分给了多个子问题。这个辨析对我来说特别有用因为很多算法教材会把减治和分治混在一章里讲做题时如果不区分分析会出大问题。4.4 一份可复用的排查清单把上面这些错误沉淀成清单实操时对着检查能省下不少调试时间。递归边界规模为2的子问题是否只需1次比较边界值有没有和递推式互相印证合并代价递推式中的常数2是不是真的对应“两次比较”有没有漏掉其他操作候选集合是否真的缩小了一半范围如果不是说明分组信息没有被正确复用。最终结论是精确次数还是渐近复杂度题目要什么你就答什么。代码实现时奇数n的“落单元素”有没有被包含进候选集合这是实现细节里最容易漏的。清单的第五项值得多解释一句。当n为奇数时分组后剩下一个单独元素它其实既是最大值候选也是最下值候选。标准处理方法是把落单元素复制进两个候选集合但这样会让候选集合的大小不是精确的n/2推导时要用(n-1)/2去算最后结论依然是3n/2-2但有个取整的细节。考试时如果题目标注n为偶数那可以省掉这个烦恼如果没有标注稳妥起见写明“n为奇数时结论为3n/2 - 3/2”或者直接说上取整这个问题就圆满了。5. 从习题到工程这套分析框架的迁移价值5.1 习题里的分治工程里的归并与快排习题2.4里练出来的递推分析能力最直接的工程迁移对象是归并排序和快速排序。归并排序的递推式T(n)2T(n/2)O(n)你肯定见过但你可能没想过如果你能精确计算合并阶段每次比较的次数就能推导出归并排序在最坏情况下的精确比较次数上界nlog2n - n 1。这个数字在数据库外部排序、大规模数据归并场景下是估算I/O次数的基础。我自己在做大数据量排序方案选型时就经常用这些精确界来估算耗时时长比直接跑基准测试快得多。快速排序也是同理。很多人背下了“快排平均O(n log n)”但当你真的需要为某个低延迟系统选择排序算法时你会关心常数系数——快排的常数系数比归并小所以在内存数据排序时通常更快。这个“常数系数意识”就是从习题2.4这类题目里训练出来的。说到底算法分析课上学到的不是某个具体算法而是一套评估工具让你在面对真实问题时能快速判断哪个方案更划算。5.2 对手论证与信息论直觉回到前面埋的伏笔怎么证明3n/2-2是最优比较次数。这里我只想给你一个直觉层面的启发不展开完整证明。想象你是一个裁判手里有一堆元素参赛者每次可以比较两个元素你要通过这场比赛同时找出最大和最小。每一次比较的结果最多能帮你排除一个元素成为最大值的可能同时排除一个元素成为最小值的可能。要让n-1个元素都失去当最大值的资格至少需要n-1次“有效信息”同理要让n-1个元素都失去当最小值的资格也需要n-1次“有效信息”。如果一次比较能同时提供两类信息那理想情况下总次数就是3n/2-2因为极限情况是某些比较同时服务于两个目标。这种“信息论式”的思考方式在算法设计里非常有用比如基于比较的排序下界nlog2n的证明用的也是同一套逻辑。你不需要背住每个下界的完整证明但如果你能从习题2.4里建立起“算法效率受限于信息获取效率”这个直觉那么以后遇到任何“最优算法”问题你都不会轻易相信“某人说这个已经最优了”而会自己从信息量角度掐指一算这个习惯在技术决策中特别宝贵。5.3 这道题还能怎么扩展最后聊一点扩展方向。习题2.4的分治思想可以轻松迁移到“同时求最大和第二大”、“找前k大元素”、“TOP-K问题”这些变体上。比如同时求最大和第二大朴素做法是先找最大n-1次再去掉最大后找最大n-2次总计2n-3次但用分治思路锦标赛法只需要nlog2n-2次。这个思路在流式计算和推荐系统里其实就是“第二好”候选比如广告召回场景里需要同时保留最优和次优结果锦标赛法就派得上用场。另一个扩展方向是并行计算。分治结构天然适合并行——两个子问题互不依赖可以交给两个线程同时算最后合并阶段成本极低。这就是为什么MapReduce框架里很多算法的核心都是分治结构。你在习题2.4里练的这10分钟推导放到分布式场景下对应的就是“如何设计一个并行求MAX/MIN的任务让通信开销最小”。一道课后题能延伸出这么多东西说实话我也是写到这里时才更清晰地感受到算法设计的学习确实是在打地基。6. 实操中我总结的三条经验第一永远不要跳过朴素方案直接写最优方案。很多参考答案直接给出分治解法导致学生误以为这就是标准思路但事实上“先想朴素方案再找浪费点再优化”这套方法本身才是可迁移的能力。你先写一版暴力双扫描再思考信息是否被复用这个思考过程的价值比算法本身大得多。第二把每道题的分析写成“三层结构”。第一层是直觉一句话说清楚为什么能优化第二层是精确分析推导出具体的比较次数第三层是渐近结论用主定理或大Theta记号给出理论定位。三层都写完整这道题才算真正吃透。我见过太多人只停留在一层或两层结果面试一被追问就露馅。第三也是我最想说的做算法题不要贪多贪透。与其一天刷十道题然后全部遗忘不如一周彻底搞懂像习题2.4这样的一道题——搞懂它的三种解法、两种证明方法、五类常见错误再把它和学过的其他算法串起来。你会发现当量积累到一定程度算法分析的很多技巧都是相通的。至少我回想自己当年啃算法的那段时间真正让我开窍的不是题的数目而是某几个特别经典的题目被反复琢磨之后的顿悟。习题2.4就是很适合作为这个顿悟起点的题目之一。