分治算法：从递归树到合并结果

我真正开始理解“分治算法：从递归树到合并结果”，不是在背完某段代码之后，而是在一次次写错之后。最明显的问题是：我以前把分治理解成“写一个递归函数”，没有真正注意子问题怎么拆、结果又为什么能够合并。把这些错误重新摊开来看，我才找到比口诀更可靠的理解方式。

分治是一种非常基础的算法思想：把一个大问题拆成若干个规模更小、结构相同的子问题，分别解决，再把子问题答案合并成原问题答案。

归并排序、快速排序、二分查找、树的递归处理、最近点对、线段树构建，都带有分治味道。它不是某一个算法，而是一种拆问题的方法。

它从哪里来

分治思想早于现代计算机：二分查找就是不断缩小范围。电子计算时代，冯·诺依曼在 1945 年前后描述的归并排序展示了典型框架——拆成子问题、分别解决、再合并结果。分治因此成为算法设计的基础范式。

分治的三步

分治递归树

图：分治先拆分，再求解，最后合并

分治通常有三步：

Divide：把原问题拆成子问题。
Conquer：递归解决子问题。
Combine：合并子问题结果。

如果子问题之间不独立，或者合并成本太高，分治就未必合适。

归并排序里的分治

归并排序是最标准的分治例子。

void mergeSort(int[] nums, int left, int right, int[] temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid, temp);
    mergeSort(nums, mid + 1, right, temp);
    merge(nums, left, mid, right, temp);
}

它的复杂度可以从递归树看：

每层合并总成本是 O(n)。
一共 log n 层。
总时间是 O(n log n)。

这比“看到递归就害怕”靠谱得多。递归复杂度不是猜出来的，而是看每层成本和层数。

快速排序里的分治

快排也用分治，但它和归并有一个关键区别：

归并排序先拆，最后合并。
快速排序先分区，让 pivot 到正确位置，再递归两边。

如果 pivot 每次都把数组切得比较均匀，快排平均 O(n log n)；如果每次都切成一边空、一边 n-1，就会退化成 O(n²)。

所以快排的工程实现通常会使用随机 pivot、三数取中、三路切分等策略。

分治和递归的关系

分治通常用递归实现，但递归不一定都是分治。

比如链表求长度是递归，但没有明显的“拆成多个子问题再合并”。归并排序、树的左右子树处理，则更典型地体现分治。

判断一个问题是否适合分治，可以问：

原问题能不能拆成同类子问题？
子问题之间是否相对独立？
子问题答案是否容易合并？
拆分是否能明显降低规模？

分治常见模式

模式	典型问题	合并方式
二分缩小	二分查找	不需要合并
左右递归	归并排序、树问题	合并左右答案
分区递归	快速排序、快速选择	pivot 定位
多路分治	大整数乘法、矩阵算法	多个子结果组合
区间分治	线段树、区间统计	汇总区间信息

工程场景

分治在工程中常用于：

大文件排序：拆分、排序、归并。
多线程任务拆分：把任务切成多个子任务并行执行。
区间统计：线段树、分块计算。
日志聚合：按时间段拆分再合并。
搜索和索引构建：分片处理后合并结果。

分治天然适合并行，但并行不是免费的。拆得太碎会导致调度、内存和合并成本上升。

常见错误

终止条件不正确，导致无限递归。
子问题范围重叠或漏掉元素。
合并逻辑复杂度太高，抵消拆分收益。
忘记考虑递归栈空间。
快排 pivot 选择不稳，极端数据退化。

面试题

分治和递归有什么区别？
归并排序为什么是 O(n log n)？
快排为什么平均快但最坏会退化？
分治适合并行吗？有什么代价？
什么样的问题不适合分治？

小结

分治的价值在于把复杂问题拆成可控的小问题。它不是“递归一下”这么简单，而是要保证拆分合理、子问题独立、合并高效。理解分治之后，排序、树、区间算法都会更顺。