【算法图解】分治思想：大问题拆小问题

分治（Divide and Conquer）是算法世界最强的“降维打击”之一。

它的直觉非常朴素：

把一个大问题拆成若干个相同结构的小问题，小问题解决后再合并回去。

但真正掌握分治，你需要的不只是口号，而是：

什么时候适合分治？什么时候是“硬套递归”？
拆到什么粒度才对？
合并成本如何影响复杂度？
如何写出不爆栈/不退化的实现？

这篇文章把分治讲成一套可复用的方法。

1. 分治的标准三步

任何分治题，你都可以用这三步写解法：

Divide（分）：把规模 $n$ 的问题拆成若干个规模更小的子问题
Conquer（治）：递归解决子问题（直到 base case）
Combine（合）：把子问题答案合并成原问题答案

你也可以把它记成一个“面试可复述”的模板：

我先定义子问题与递归边界。
然后递归求解左右子问题。
最后在合并阶段把两边结果组合成最终答案。

2. 分治什么时候有效？关键看“合并成本”

分治不是免费的。

它通常会带来：

递归开销（函数调用、栈深度）
合并开销（把子结果拼起来）

决定复杂度的核心是递推式：

$$T(n) = a,T(n/b) + f(n)$$

$a$：子问题个数
$b$：每个子问题规模缩小倍数
$f(n)$：合并阶段做了多少工作

直觉：

如果 $f(n)$ 很小（比如 $O(1)$），分治往往能做到 $O(\log n)$ 或 $O(n)$
如果 $f(n)$ 很大（比如 $O(n)$），就会变成经典的 $O(n\log n)$
如果 $f(n)$ 甚至更大，分治可能得不偿失

3. 例子一：二分查找（分治的最简形态）

二分是分治的“入门级冠军”。

Divide：每次把区间砍半
Conquer：递归到左半或右半
Combine：不需要合并（直接返回答案）

复杂度：

$T(n)=T(n/2)+O(1)$
所以时间 $O(\log n)$，栈空间 $O(\log n)$（递归写法）

工程建议：二分尽量用迭代写，避免栈。

4. 例子二：归并排序（合并阶段是关键）

归并排序完整体现了分治：

Divide：拆成左右两半
Conquer：递归排序
Combine：合并两个有序数组

合并成本是 $O(n)$，递推式：

$T(n)=2T(n/2)+O(n)$
时间 $O(n\log n)$
空间通常 $O(n)$（需要辅助数组）

分治能把排序做到 $O(n\log n)$ 的关键原因：

每层合并总成本是 $O(n)$
层数是 $\log n$

5. 例子三：快速排序（分治 + 随机化避免退化）

快排也是分治，但“合并阶段”很特别：

Divide：按 pivot 分区，把小的放左边，大的放右边
Conquer：递归排左右两边
Combine：不需要显式合并（分区已经把 pivot 放对位置）

平均时间 $O(n\log n)$，但最坏 $O(n^2)$。

工程上避免退化的常用手段：

随机 pivot
三数取中
小数组改用插排
递归深度过深时切换到堆排（introsort 思路）

6. 例子四：最大子数组和（分治解法如何“写对合并”）

问题：给定数组，求连续子数组的最大和。

分治思路：

Divide：中点拆成左右
Conquer：求左边最大子数组、右边最大子数组
Combine：还需要求“跨中点”的最大子数组（左边最大后缀 + 右边最大前缀）

最终答案是三者最大：

leftMax
rightMax
crossMax

这里的关键就是：

合并阶段要能在 $O(n)$ 或更低成本拿到 crossMax。

它的复杂度是 $O(n\log n)$；但这个题的最优解是 Kadane（动态规划）$O(n)$。

这也提醒你：

分治不一定最优
但它经常是“结构清晰、容易正确”的强力方案

7. 什么时候不该用分治？

常见反例：

合并阶段接近 $O(n^2)$（例如需要两两比较、全量重建）
子问题之间强耦合，无法独立求解
可以用线性扫描/贪心/DP 一次解决

面试里你可以补一句体现判断力：

“我能用分治写 $O(n\log n)$，但这里其实有 $O(n)$ 的 DP/贪心更优。”

8. 实战落地：写分治时的 4 个检查点

base case 是否覆盖空/单元素？
子问题是否严格变小？（避免无限递归）
合并逻辑是否只依赖子结果？
递归深度是否可能爆栈？（必要时迭代/显式栈）

总结

分治的三步：分、治、合。
决定复杂度的关键是合并成本 $f(n)$。
归并/快排/二分都是分治范式的经典代表。
会分治，不是会背，而是能写出正确的递推与合并。

【算法图解】分治思想：大问题拆小问题

相关标签