分治

一句话

分治不是"递归" - 是"先分解、再合并解"的程序结构. 它刻意要求合并(merge)开销可控, 否则甚至比分而治之之前还不划算. 很多工程上人称"分治"的代码其实只是"递归调用", 实质不是分治 (如mers 是"分 + 合并行将"), 看清楚"merge 在哪儿"就看清结构.

模板

solve(P):
  if base case: return answer
  分 P = P1 ∪ P2
  A1 = solve(P1), A2 = solve(P2)
  return combine(A1, A2)

经典案例: 归并排序、快速排序 (partition 是 pivot 排序)、Karatsuba 大整数乘法、最近点对 / 平面最近距离、二分搜索 (信息修改)、线段树 / 主席树基础.

复杂度主定理回顾

T(n) = a·T(n/b) + f(n), 结论见 复杂度分析.

经典: 最近点对 (平面)

O(n log n):

1. 按 x 排序, 递归左侧和右侧;
2. 合并时只考虑横跨分界线 ± δ 的点 (δ = 左右解最小值), 按 y 排后需检查每点附近 6 个点.

经典: 求逆序对

归并排序的副产物 O(n log n): 归并过程中"左半还剩 m 个值时, 从右半取的数所对应的逆序数加 m".

工程多核化

分治天然适合 fork-join 工作窃取. 但分到原子 (n ≤ 1024) 就停下, 否则 fork 开销 > 收益.

硬件视角: 分治的递归树形结构很难 GPU/FPGA 并行化, 但在分完之后的所有 leaf 任务可以 SIMD - 这就是分治在 NPU 编译器里的用法.

易错

1. merge 非 in-place: 归并排序需要 O(n) 辅助空间, 原地归并虽存在但常数大、专利多.
2. base case 边界: n=1 / 0 都写好.
3. 并发分治: fork-join 框架天然适合分治, 但要测"分到多大才 fork", 否则细粒度 fork 开销 > 收益.