分治算法（Divide and Conquer）
分治算法是「分解问题」思维模式的典型应用：将大问题分解为独立的子问题，分别解决后合并结果。
定义
分治算法（Divide and Conquer）是一种算法设计范式，将大问题分解成若干个规模较小、相互独立、与原问题性质相同的子问题，递归地解决这些子问题，然后合并其结果得到原问题的解。
核心思想：分而治之——分解（Divide）、解决（Conquer）、合并（Combine）
分治思想 vs 分治算法
| 维度 | 分治思想（广义） | 分治算法（狭义） |
|---|---|---|
| 范围 | 所有分解问题的递归思路 | 分解后求解效率高于直接求解的递归算法 |
| 效率要求 | 无（有些问题只能分解求解） | 必须满足分解后复杂度更低 |
| 典型示例 | 斐波那契递归、二叉树节点计数、动态规划 | 归并排序、桶排序、合并K个升序链表 |
| 直接求解对比 | 不存在"直接求解"的替代方案 | 存在直接求解的更低效方案 |
关键判断标准：是否存在"不分解直接求解"的方案？如果有且分解后更高效，才是分治算法。
复杂度降低原理
数学类比：$(a+b)^2 = a^2 + 2ab + b^2 \geq a^2 + b^2$
- 原问题规模 $N=a+b$，直接求解 $O(N^2)$ 复杂度为 $O((a+b)^2)$
- 分解为子问题后分别求解，复杂度为 $O(a^2 + b^2) < O((a+b)^2)$
- 适用边界：仅多项式级别 $O(N^k)$ 的算法可能通过分治提升效率，指数级算法不适用
核心特性
| 特性 | 说明 |
|---|---|
| 问题分解 | 原问题分解为若干子问题 |
| 子问题独立 | 子问题之间没有重叠（区别于动态规划） |
| 递归求解 | 子问题与原问题性质相同，递归求解 |
| 结果合并 | 将子问题的解合并为原问题的解 |
分治 vs 动态规划
| 维度 | 分治算法 | 动态规划 |
|---|---|---|
| 子问题关系 | 独立不重叠 | 重叠 |
| 递归树 | 每个子问题只计算一次 | 子问题会重复计算 |
| 是否需要记忆化 | 不需要 | 通常需要 |
| 示例 | 归并排序、快速排序 | 斐波那契（带记忆化） |
关键区别：分治算法的子问题是独立的，动态规划的子问题是重叠的。
三步骤
- 分解（Divide）：将原问题分解为若干个规模较小的子问题
- 解决（Conquer）：递归地解决这些子问题（子问题足够小时直接求解）
- 合并（Combine）：将子问题的解合并成原问题的解
经典算法
| 算法 | 分解方式 | 合并方式 | 时间复杂度 |
|---|---|---|---|
| 归并排序 | 分成左右两半 | 合并两个有序数组 | O(n log n) |
| 快速排序 | 按 pivot 分成左右 | 无需合并（原地排序） | 平均 O(n log n) |
| 二分查找 | 分成左右区间 | 无需合并（只走一边） | O(log n) |
| 最近点对 | 按 x 坐标分成左右 | 合并中间区域的候选点 | O(n log n) |
| 大整数乘法 | 按位分解 | 合并部分积 | O(n^1.59) |
| 桶排序 | 分成若干个桶 | 对各桶分别排序后合并 | O(n)（平均） |
归并排序：典型分治
分解：将数组分成左右两半 解决：递归地对左右两半排序 合并：合并两个有序数组
void mergeSort(int[] arr, int left, int right) {
if (left >= right) return; // base case
int mid = left + (right - left) / 2;
// 分解
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并
merge(arr, left, mid, right);
}
递归树理解：归并排序的递归树是二叉树，后序遍历（先排左右，再合并）。
快速排序：另一种分治
分解：选择 pivot，将数组分成左右两部分 解决：递归地对左右两部分排序 合并：无需合并（原地排序，pivot 已在正确位置）
void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
// 分解：partition 返回 pivot 的最终位置
int p = partition(arr, left, right);
// 解决：递归排序左右
quickSort(arr, left, p - 1);
quickSort(arr, p + 1, right);
// 合并：无需合并
}
递归树理解：快速排序的递归树是二叉树，前序遍历（先排好 pivot，再排左右）。
适用场景
- 问题可以分解：原问题能分解为相似的子问题
- 子问题独立：子问题之间没有依赖关系
- 合并可行：子问题的解能高效地合并
时间复杂度分析
分治算法的时间复杂度通常用主定理（Master Theorem）分析：
T(n) = aT(n/b) + f(n)
| 情况 | 条件 | 时间复杂度 |
|---|---|---|
| 情况1 | f(n) = O(n^c)，c < log_b(a) | O(n^log_b(a)) |
| 情况2 | f(n) = Θ(n^log_b(a) * log^k(n)) | O(n^log_b(a) * log^(k+1)(n)) |
| 情况3 | f(n) = Ω(n^c)，c > log_b(a) | O(f(n)) |
示例：归并排序 a=2, b=2, f(n)=O(n) → T(n) = O(n log n)
注意事项
- base case 要正确：递归终止条件必须正确
- 子问题要独立：这是与动态规划的关键区别
- 合并操作要高效：如果合并代价太高，分治可能不划算
相关概念
参考资料
- 理解递归框架：分治算法是分解问题思维的体现
- 归并排序-总结：归并排序完整实现
- 快速排序算法：快速排序完整实现
- 算法总结：算法框架思维总结
- 分治算法解题套路框架：分治思想与分治算法的区别、复杂度降低原理