优选算法这个系列写到分治专题其实是很多人的分水岭。前面几章讲遍历、双指针、动态规划多少还有套路可循一进入分治问题就变成了为什么这道题要拆成两半拆完之后又要做哪些额外动作更扎心的是递归代码一看就懂一关掉视频自己写就错。我做过一段时间算法相关的辅导发现大多数人卡住的点根本不是递归不会写而是没搞清楚分治真正的工作量在哪里。这篇文章我就按自己的理解把分治从直觉、复杂度、经典题到实战高频坑完整过一遍适合正在刷算法题、准备面试或竞赛的读者也适合工作里偶尔需要手写复杂算法的人。1. 分治的直觉与其说是拆不如说是借1.1 从三个小问题看分治的通用动作先聊几个特别朴素的问题。问题A在一堆扑克牌里找最大的一张。大多数人会一张张看这没问题。但如果是两个人合作找呢一个人看前一半一个人看后一半各自找到最大值再比较一下就能确定整副牌的最大值。这就是分治。问题B统计一个数组里有多少对逆序前面的数比后面大。直接两层循环当然是O(n^2)但如果你手头刚好有归并排序的框架把数组拆成两半先统计左半内部的逆序对、右半内部的逆序对再统计一个在左一个在右的逆序对三部分加起来就是答案。关键是第三部分可以在合并两个有序数组的过程中顺带算出来复杂度直接降到O(n log n)。问题C在一个有序数组里找某个元素。二分查找几乎人人都学过但你有没有想过它本质上就是每次把问题拆成左边一半和右边一半然后只进入其中一半继续做同样的操作。它之所以快是因为每一步都丢弃了一半的规模。这三个问题放在一起你会发现分治的固定动作其实就三个分解把原问题切分成若干子问题、解决递归处理或者直接解决足够小的子问题、合并把子问题的结果汇总成原问题的答案。不同题目的差别只在于切的方式、子问题的数量、以及合并动作的复杂度。1.2 分很容易合才是灵魂很多教程讲分治会把大量篇幅放在递归两个字上仿佛只要会写递归就会分治。我的感受恰恰相反递归调用这一段几乎不用动脑子真正决定解法优劣的永远是拆完之后你要额外做的合并动作。打个比方分治像公司拆任务。把一个大任务拆给两个小组这是分每个小组自己内部搞定这是治但你最后肯定要有人把两边的成果汇总、解决边界衔接问题这就是合。很多问题难就难在两边各做各的都很顺利一到交接就出Bug。比如最大子数组问题在一个数组里找连续的一段使段内数字之和最大。如果只知道用前缀和或者暴力枚举确实也能做。但用分治的思路是数组从中间劈开答案只可能是三种情况之一——完全在左半边、完全在右半边、跨越中间线。前两种交给递归第三种必须由你写一个从中间向左扫一遍再向右扫一遍的循环来完成。这个跨越中间的合并逻辑才是整道题的核心考点。所以学分治建议你每看完一道题都问自己这道题的合并阶段做了什么为什么合并阶段的复杂度和递归加在一起仍然可控这两个问题想明白了分治就算入门了。1.3 分治、动态规划、贪心到底怎么区分学算法的人都会纠结这道题到底用分治还是DP其实两者有非常清晰的分界线。分治的子问题是互不重叠的左边归左边右边归右边最多在合并时跨过边界扫一遍。它不依赖把同一个子问题的结果存下来复用因为根本不会重复计算同一个子问题。动态规划的子问题则是相互重叠的f(i) 的计算可能依赖 f(i-1) 甚至 f(i-2)同一个值会被反复需要所以你要用表格把它记下来。贪心则更进一步它根本不在子问题之间做比较而是每一步选当前看起来最好的放弃尝试所有拆分方案的机会。所以拿到一道题先判断子问题之间会不会互相重复。会重复考虑DP不会重复且合并动作有明确意义考虑分治。这两个判断差不多能筛掉一半的纠结。剩下少数的题其实殊途同归比如最大子数组问题Kadane算法只用一遍扫描就解决了但它的正确性证明里依然能看到分治的思考痕迹。2. 复杂度分析主定理要会推不能只会背2.1 递归树比公式更直观许多算法书会把主定理Master Theorem写成三个Case然后让学生死记。我的建议是公式要理解但最开始一定要用递归树把形状画出来。以归并排序为例T(n) 2T(n/2) O(n)。这棵树长什么样根节点是规模为n的合并操作开销O(n)下一层有两个节点每个规模n/2合并开销O(n/2)总计O(n)再往下有四个节点每个规模n/4总开销还是O(n)。这样的层一共有log2(n)层每层开销都是O(n)所以总复杂度是O(n log n)。这个每层开销相同的情况对应的就是 f(n) 刚好等于 n^(log_b(a)) 的量级。这里的a是每次拆出的子问题个数b是规模缩小的倍数。归并排序每次拆2个、规模减半log_b(a) log2(2) 1而 f(n) n 也确实是一次的所以每层总开销恒定。画出递归树之后主定理的三个分支其实就是三句话如果根节点的合并开销比叶子节点数增长慢总开销由叶子数决定也就是 n^(log_b(a)) 主导如果两者同量级每一层的开销都一样总开销就是每层开销乘以层数如果根节点的开销主导那总开销基本上就是合并部分的开销 f(n)。用这个视角去判断哪个量级是主导比死记三个Case靠谱得多。尤其遇到a不是整数、b不是2的情况画出两层递归树很快就能看出趋势。2.2 一个括号就能拆掉主定理的坑主定理最大的坑在于 f(n) 里的 n 到底代表什么。我见过很多人在一道把数组分成5份每份规模是原来的1/3合并开销是O(n^2)的题目上翻车原因是他们一看 f(n) n^2就兴奋地套用Case 3却忘了先算 n^(log_b(a)) 是多少。这里a5b3log3(5)约等于1.465。n^1.465和n^2相比后者增长更快说明合并开销主导所以答案是O(n^2)。如果你不动笔算仅凭5个分支规模1/3就猜一个O(n log n)那就大错特错了。分治复杂度的计算本质上就是比较两个东西谁长得快递归过程产生的叶子节点总数和每次合并动作的开销。叶子节点数由拆分方式决定合并开销由题目本身的性质决定。这两个量级之比直接锁定了最终复杂度。所以做题时养成习惯每次写完递归式先在草稿纸上画两层递归树算出n^(log_b(a))再比较大小。这个习惯比记任何公式都有用。2.3 把合并开销算丢我犯过的典型错误分享一个我自己实际犯过的错误。有一道题要求把数组分成两半递归处理合并阶段需要把两个部分的所有元素两两比较一遍。我当时想合并时如果不做任何优化对每对元素比较一次那就是O(n^2)。但我直接写了递归式 T(n) 2T(n/2) O(n^2)算出来总复杂度是O(n^2)。解法当然不是错的只是没有任何意义因为排序后整体扫描的复杂度也是O(n^2)甚至更低分治没有带来任何收益。这个问题的本质在于分治的价值在于让合并动作的总开销低于直接面对整个数组的开销。归并排序的合并是O(n)的虽然每层都要扫一遍但每层只扫一次总开销O(n log n)如果你的合并动作是O(n^2)那每层开销随着树往上快速膨胀最终根节点的开销直接把叶子层的收益吞掉。所以拿到一道分治题先不要急着写递归先估算合并开销。如果合并开销看起来无法压到O(n)或者O(n log n)以下这道题八成不适合用分治做或者需要换一种合并策略。这个判断能帮你省下大量瞎写递归的时间。3. 四个必须手撕的经典场景分治的经典例子很多但真正值得反复手撕的我认为是四个逆序对计数、最大子数组、最近点对、快速幂。前两个帮你掌握合并阶段怎么写第三个帮你理解分治为什么能减少比较次数第四个则是分治思想在非数组问题上的典型延伸。3.1 逆序对计数归并排序的副产品题目背景是给一个数组统计有多少对(i, j)满足 i j 且 arr[i] arr[j]。直接两层循环是O(n^2)数据规模到10万就基本卡死需要优化到O(n log n)或更优。分治解法其实就三步把数组从中间劈开先统计左半内部的逆序对统计右半内部的逆序对统计一个在左、一个在右的逆序对。前两步递归就行。第三步怎么高效做关键在两边各自有序这一点上。如果左右两边都已经排成升序那么对于右半的某个元素 arr[j]左半中所有比它大的元素 arr[i]i在左半范围内都和它构成逆序对。而左半已经有序所以可以用二分找到第一个大于arr[j]的位置左半从那个位置到结尾的所有元素都是答案。但更常见的做法是直接在归并排序的合并过程中顺便统计合并两个有序数组时每当从右半取出一个元素放入结果数组说明左半当前的剩余元素都大于它于是答案累加左半剩余元素的数量。贴一个最直接的Python实现def merge_sort_count(arr): if len(arr) 1: return arr, 0 mid len(arr) // 2 left, inv_left merge_sort_count(arr[:mid]) right, inv_right merge_sort_count(arr[mid:]) merged [] inv inv_left inv_right i j 0 len_left, len_right len(left), len(right) while i len_left and j len_right: if left[i] right[j]: merged.append(left[i]) i 1 else: merged.append(right[j]) j 1 inv len_left - i # 左半从i到末尾都大于right[j] merged.extend(left[i:]) merged.extend(right[j:]) return merged, inv这里的关键就是一行inv len_left - i。只有从左半取数时才不增加逆序对计数因为左半元素本来排在前边从右半取数时说明左半从当前位置开始往后的所有元素都会大于当前取出的右半元素这些全部构成逆序对。这个题的训练价值在于让你明白合并阶段不一定要额外遍历跨区间的元素而是可以在已有操作排序合并里顺带完成统计。这种思路在竞赛和面试里特别重要因为它通常能把额外的时间开销压到零。提示如果你对为什么左右各有序很关键还不清楚建议手写一个长度为3的数组把归并过程一步步画出来。画完整个过程你大概率就不再需要背这段代码了。3.2 最大子数组答案必然藏在三种位置之一给定数组找一段连续子数组使和最大。这个问题用Kadane算法一遍扫描就能解但分治版本是理解跨区间合并最好的入门题。思路是把数组从中点分成两半。最终的最大子数组只可能是完全在左半完全在右半跨过中点也就是从中间往左延伸一段、再往右延伸一段。前两种递归返回第三种需要单独计算。怎么算从中间开始向左扫记录累加过程中的最大值再从中间加一向右扫记录累加过程中的最大值。两个最大值相加就是跨中点的最大子数组和。核心代码片段def max_crossing(arr, left, mid, right): left_sum float(-inf) cur 0 for i in range(mid, left - 1, -1): cur arr[i] left_sum max(left_sum, cur) right_sum float(-inf) cur 0 for j in range(mid 1, right 1): cur arr[j] right_sum max(right_sum, cur) return left_sum right_sum然后递归主体就是分别求左、右、跨中点的最大值三者取max。def max_subarray(arr, left, right): if left right: return arr[left] mid (left right) // 2 left_max max_subarray(arr, left, mid) right_max max_subarray(arr, mid 1, right) cross_max max_crossing(arr, left, mid, right) return max(left_max, right_max, cross_max)复杂度上每层递归都要做一次O(n)的跨中点扫描递归层数O(log n)所以总复杂度O(n log n)。虽然不如Kadane的O(n)但它的意义在于你不会只在线性扫描能解决的问题上打转而是能看到分治如何把任意位置的问题变成三种确定位置的问题。我练习这个题时的最大收获是真正理解了什么叫做把未知问题转化成已知子问题。最大子数组的任意位置是不可枚举的但一旦你把它分类为左、右、跨中点每一类都有确定的求法题目就变得可做了。3.3 最近点对常数优化绝不是抠细节平面上给n个点找距离最近的两个点。暴力做法两两比较O(n^2)。用分治可以压到O(n log n)而且这个压制的思路比代码本身更重要。基本流程按x坐标排序从中间分成左右两半递归求左半最近点对距离d1右半最近点对距离d2取d min(d1, d2)关键一步只考虑x坐标在中点横坐标±d范围内的点也就是可能跨过中点且距离小于d的点对对这些点按y坐标排序然后依次检查相邻的点一旦两个点y坐标差超过d就停止内层循环因为后面的点不可能更近。很多人以为第4步只是常数优化其实不是。它把最差情况下的比较次数限制在一个很小的常数内。原因是从候选集中任取一点以它为中心、d为边长的一个区域内最多只能有常数个点——否则左右半内部必然出现更近的点对这与d的定义矛盾。这里贴一个结构清晰的Python版本重点看分治的骨架和合并阶段的剪枝逻辑import math def brute_force(points): n len(points) best float(inf) for i in range(n): for j in range(i 1, n): best min(best, dist(points[i], points[j])) return best def dist(p, q): return math.hypot(p[0] - q[0], p[1] - q[1]) def closest_pair(points): if len(points) 3: return brute_force(points) mid len(points) // 2 mid_x points[mid][0] left_res closest_pair(points[:mid]) right_res closest_pair(points[mid:]) d min(left_res, right_res) strip [p for p in points if abs(p[0] - mid_x) d] strip.sort(keylambda p: p[1]) for i in range(len(strip)): for j in range(i 1, len(strip)): if strip[j][1] - strip[i][1] d: break d min(d, dist(strip[i], strip[j])) return d很多初学者写这道题时会漏掉只取±d范围内点的剪枝然后发现复杂度依然是O(n^2)于是断言分治没用。实际只要这个剪枝加上复杂度就能从O(n^2)降到O(n log n)。这道题真正的坑在于排序策略。如果每一步都在递归内部重新按x排序复杂度会退化成O(n log^2 n)甚至更差。正确的做法是先在外面按x排序一次递归分割时直接截取区间这样排序开销不会重复。按y排序这一步严谨的做法是在合并阶段用归并排序按y合并能保持全程O(n log n)如果你只是为了理解每次递归里临时sort也能跑出正确答案但要清楚它多了一个log。3.4 快速幂分治思想不是只能切数组如果只把分治理解成数组从中间切开你会错过一个非常实用的场景——快速幂。计算a^n最朴素的做法是乘n次O(n)。但如果你用分治视角看a^n可以写成如果n是偶数a^n (a^(n/2))^2如果n是奇数a^n a * (a^((n-1)/2))^2每次规模减半合并动作是常数次乘法复杂度O(log n)。递归版可以写成def fast_pow(a, n): if n 0: return 1 if n % 2 1: return fast_pow(a, n - 1) * a half fast_pow(a, n // 2) return half * half但结合实际场景递归版有一个小问题n很大时递归调用栈会占用额外空间而且有人会不小心把fast_pow(a, n // 2)写两遍造成重复计算。我更推荐迭代版的二进制分解写法def fast_pow_iter(a, n): res 1 base a while n 0: if n 1: res * base base * base n 1 return res这两种写法本质是同一个思想但迭代版省掉了递归栈。如果题目要求结果取模就在每步乘法后取模注意中间值溢出问题。快速幂的启发是分治的切分对象可以是抽象的规模参数不一定是物理上的数组区间。之后你会看到许多数学计算、矩阵乘积、斐波那契数列加速都复用同一个规模减半、合并结果的模式。所以学分治一定要跳出切数组的思维定式。4. 分治实战里的高频坑合并、边界、全局状态这一节完全来自我在刷题和带人过程中反复见到的错误。分治代码看起来短但一错就非常隐蔽因为它不是错在语法上而是错在思维逻辑上。4.1 合并阶段漏掉跨区间的情况这是分治题里最常见的坑。典型症状递归到底层返回的结果是正确的但整体答案不对而且往往是偏小。最大子数组题最容易演示这个问题。如果你只写了return max(left_max, right_max)而忘了cross_max你会发现对于 [1, 2, 3, -1, 4, 5] 这种正数连在一起的数组答案就会错。因为最大的子数组可能横跨中点比如 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 这个经典例子最大子数组 [4, -1, 2, 1] 恰好跨越中点。排查这类错误的方法很简单造一个明确跨越中点的测试用例比如 [2, -1, 2]最大子数组是 [2, -1, 2]和是3恰好跨越中点。如果递归返回2而不是3那基本可以确定合并阶段漏写了跨区间逻辑。所以凡是答案可能是任意连续区间的题都要认真想想合并时要不要额外枚举一种跨中点的情形最大子数组、和为特定值的连续子数组计数、某些区间最值类问题都有这个隐患。4.2 递归基不是越小越稳另一个常见认知是递归基设得越小越安全于是有人把归并排序的递归基设为数组长度为0。听起来严谨但会导致一个尴尬的问题长度是1的数组还要再切分吗长度是0的数组从哪里切分这些都需要额外分支处理。更合理的递归基是len(arr) 1。长度为0或1都直接返回不需要再切分。对于最近点对这类问题递归基通常设为 n 3因为3个点以内直接暴力比较比递归更快也避免分割线出现左空右空的边界灾难。递归基的选择原则是让递归在合法、有意义的最小规模上停止同时保证这一步不需要依赖下一层递归的结果。多花30秒想清楚递归基能帮你避免大量越界运行错误。4.3 中位数和下标偏移两种写法不可混用分治里最经典的边界陷阱除了递归基还有取中点和区间表示方式。我在这上面栽过多次后来总结出一套固定的写法Python习惯左闭右开 [left, right)mid left (right - left) // 2递归调用 [left, mid) 和 [mid, right)。C里则常写左闭右闭 [left, right]mid left (right - left) // 2递归调用 [left, mid] 和 [mid 1, right]。两种都能写对就怕混着用。我见过最经典的错误是一个人用左闭右闭的区间定义却把递归调用写成了[left, mid]和[mid, right]这样mid位置的元素会被重复计算两次在计数类问题里直接导致结果翻倍。另一个细节(left right) // 2在极端情况下可能溢出C里尤其明显当left和right都接近int上限时所以更稳妥的是left (right - left) // 2。这个写法既不溢出语义也更清晰。4.4 全局变量和带返回值的递归打架有些初学者习惯用全局变量存答案。比如逆序对计数他们在递归函数内部不return计数结果而是直接累加到全局 ans 上。思路没错但很容易出两类问题多次测试用例之间忘记清空全局 ans导致结果叠加递归分支较多时某个分支提前return导致全局变量累加漏掉一部分。我建议一律用返回值递归。每层递归明确返回这层的子结果由上层合并。这样函数纯粹测试方便也不容易产生状态残留。如果确实需要在递归里更新一个临时数组比如归并排序的辅助数组尽量通过参数传入并在使用后清理避免临时内容污染下一次调用。注意遇到需要在多个测试数据上反复调用的分治函数第一件事是确认全局状态是否干净。我吃过不少亏最后发现Bug都出在上一个用例的残留数据混进了下一个用例。5. 从模板到灵活哪些题该用分治哪些不该学完前面的经典题很容易产生一种万物皆可分治的错觉。但实际做题和工作里分治并不是银弹。这一节聊一聊怎么判断以及分治思维向日常开发的迁移。5.1 能用但没必要当线性扫描足够快时我一直强调分治的价值在于把复杂度从O(n^2)或指数级降到O(n log n)甚至更低。但如果某个问题本来就有一个O(n)的线性解法分治版本通常只是徒增复杂度的练习工程上并不可取。典型例子就是最大子数组。面试官如果非要你用分治写你能写出来是加分项但如果实际业务里遇到类似需求直接用Kadane线性扫描就好不仅更快代码也更短、更不容易出错。做选型时我的优先级大致是这样有没有O(n)的扫描解法有就不用分治子问题之间是否重叠重叠就用DP或记忆化搜索问题能否通过排序、二分、堆等前置操作解决能就先想简单方案只有前面都否定或者你明确需要在比较型合并上做优化如逆序对、最近点对才考虑分治。5.2 分治解不动的问题长什么样分治也有明显不擅长的场景常见的有子问题之间存在强耦合比如最长公共子序列子问题天然重叠更适合DP答案依赖全局信息比如求整个数组的众数如果只是切两半分别统计合并时很难高效得出正确众数递归深度本身会成为瓶颈的场景比如某些链式递归O(n)深度可能把栈空间撑爆合并阶段无法压到近线性的问题分治往往带不来收益。当你发现题目满足以上特征时就可以果断放弃分治路线转去找其他解法。这不是技术不行而是算法选型的一部分。5.3 分治思维在工作中的迁移最后说一个容易被忽略的点分治思想在工程实践里比在刷题里更常见。你写的排序模块、数据库的分区合并、MapReduce的map-reduce流程、日志系统的分桶归并底层全是分治。我在实际工作中写过不少数据处理流程最常用的模式就是把一天的数据按小时切分统计再合并成全天报表把一个大文件按行数切成多个小块并行解析最后再汇总。写这些代码时我用的思考方式跟分治刷题完全一致先定义清楚原子任务的规模再定义合并规则最后处理边界和去重。所以别把分治只当成面试题它在系统设计和大数据处理里是一种基本的问题抽象方式。刷题训练收获的不只是能AC某道题而是形成一种如何把一个大规模问题切成可控小问题并正确合并的本能。分治这个专题到这里就告一段落了。回想自己学它的过程最大的心得其实是不要沉迷于递归的魔法感要时刻问自己分完怎么合。合得漂亮才叫分治合不出来那只是把一个难题拆成了一堆难题。再分享一个练习上的小技巧每做完一道分治题强制自己用文字写出分解方式、递归基、合并逻辑、时间复杂度四行总结。坚持几道以后你会发现自己对题目结构的敏感度会明显提高。这个习惯我至今还在用读别人的复杂代码时也是靠它快速定位核心逻辑。