一、什么是分治
分治（Divide and Conquer） 将一个问题递归地分解为若干个规模更小的同类子问题，分别求解后再合并结果。
三步曲：
- Divide：将问题拆成若干子问题。
- Conquer：递归解决子问题（足够小时直接求解）。
- Combine：将子问题的解合并为原问题的解。
Mermaid · 渲染中（下方为源码）
graph TD P[原问题 n] --> D1[子问题 n/2] P --> D2[子问题 n/2] D1 --> S1[子问题 n/4] D1 --> S2[子问题 n/4] D2 --> S3[子问题 n/4] D2 --> S4[子问题 n/4] S1 --> M[合并结果] S2 --> M S3 --> M S4 --> M
与 DP 的区别：分治的子问题互不重叠；DP 的子问题大量重叠。
二、分治的适用条件
| 条件 | 说明 |
|---|---|
| 可分解 | 问题能拆成规模更小的同类问题 |
| 子问题独立 | 子问题之间无公共子子问题（否则用 DP） |
| 可合并 | 子问题的解能高效合并为原问题的解 |
| 递归基 | 存在足够小的基本情况可直接求解 |
三、主定理（Master Theorem）
分治算法的复杂度通常满足递推：
[T(n) = a \cdot T(n/b) + O(n^d)]
| 情况 | 条件 | 复杂度 |
|---|---|---|
| 1 | d < log_b(a) | O(n^{log_b(a)}) |
| 2 | d = log_b(a) | O(n^d · log n) |
| 3 | d > log_b(a) | O(n^d) |
速记：
| 算法 | a | b | d | 复杂度 |
|---|---|---|---|---|
| 归并排序 | 2 | 2 | 1 | O(n log n) |
| 快速排序（平均） | 2 | 2 | 1 | O(n log n) |
| 二分查找 | 1 | 2 | 0 | O(log n) |
| Strassen 矩阵乘法 | 7 | 2 | 2 | O(n^{2.81}) |
四、经典案例
4.1 归并排序
最经典的分治：拆半 → 递归排序 → 合并。
public void mergeSort(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
private void merge(int[] arr, int lo, int mid, int hi) {
int[] tmp = new int[hi - lo + 1];
int i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi) {
tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= hi) tmp[k++] = arr[j++];
System.arraycopy(tmp, 0, arr, lo, tmp.length);
}- 时间：O(n log n)，空间：O(n)
4.2 快速幂
计算 x^n，将指数对半分：
public double myPow(double x, long n) {
if (n == 0) return 1.0;
if (n < 0) { x = 1 / x; n = -n; }
double half = myPow(x, n / 2);
return (n % 2 == 0) ? half * half : half * half * x;
}- 时间：O(log n)，空间：O(log n)
4.3 最近点对
问题：平面上 n 个点，找距离最近的一对。
分治思路：
- 按 x 坐标排序，取中线分成左右两半。
- 递归求左半最近距离
dL、右半最近距离dR。 d = min(dL, dR)。- 只需检查中线附近宽度为
2d的带状区域内的跨区点对。
// 核心合并步骤（简化）
private double closestInStrip(Point[] strip, double d) {
Arrays.sort(strip, (a, b) -> Double.compare(a.y, b.y));
double minD = d;
for (int i = 0; i < strip.length; i++) {
for (int j = i + 1; j < strip.length && strip[j].y - strip[i].y < minD; j++) {
minD = Math.min(minD, dist(strip[i], strip[j]));
}
}
return minD;
}- 时间：O(n log n)，空间：O(n)
4.4 大整数乘法（Karatsuba）
将 n 位数拆成两半：x = a·10^(n/2) + b，y = c·10^(n/2) + d
传统需要 4 次乘法，Karatsuba 只需 3 次：
z0 = b * d
z2 = a * c
z1 = (a + b) * (c + d) - z0 - z2
结果 = z2 * 10^n + z1 * 10^(n/2) + z0
- 时间：O(n^{1.585})，优于朴素的 O(n²)
4.5 数组中的第 K 大元素（QuickSelect）
public int findKthLargest(int[] nums, int k) {
int target = nums.length - k;
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int pivot = partition(nums, lo, hi);
if (pivot == target) return nums[pivot];
else if (pivot < target) lo = pivot + 1;
else hi = pivot - 1;
}
return nums[lo];
}
private int partition(int[] nums, int lo, int hi) {
int pivot = nums[hi], i = lo;
for (int j = lo; j < hi; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, hi);
return i;
}- 平均时间：O(n)，最坏：O(n²)（随机化 pivot 可避免）
五、分治 vs 其他策略
| 维度 | 分治 | DP | 贪心 |
|---|---|---|---|
| 子问题 | 独立不重叠 | 重叠 | 无子问题 |
| 求解方式 | 递归 + 合并 | 记忆化/递推 | 逐步选择 |
| 典型应用 | 排序、最近点对 | 背包、LCS | 区间调度 |
| 是否回退 | 否 | 否 | 否 |
六、分治的优化方向
- 减少递归开销：小规模时切换为插入排序（如 Java Arrays.sort 在 n<47 时用插入排序）。
- 尾递归优化：某些分治可改写为迭代（如快速幂的迭代版）。
- 并行化：子问题独立 → 天然适合多线程。
- 减少合并代价：原地归并（In-place Merge）节省空间。
七、面试常见题
- 🟢 快速幂、二分查找、合并有序数组
- 🟡 归并排序、第 K 大元素、翻转对
- 🟠 最近点对、大整数乘法、分治求逆序对
- 🔴 分治 + 线段树、CDQ 分治
八、调试技巧
- 验证 base case：n=0、n=1 时是否正确返回。
- 打印分治过程：输出每次递归的
[lo, hi]范围。 - 合并逻辑单独测试：先确保 merge 函数正确。
- 对拍：与暴力 O(n²) 对比，n≤20 随机验证。