分治法

分治把实例拆成规模严格下降、结构相同且覆盖原问题的子问题，独立求解后再组合答案。效率取决于子问题是否平衡、是否大量重叠，以及合并需要多少工作。经典分治通常不复用重叠子问题。

归并排序把数组均分、递归排序两半，再线性合并。例如 $[4,1,3,2]$ 的两半分别递归得到 $[1,4]$ 与 $[2,3]$。合并时比较两端当前首项：先输出 $1$，再输出 $2$、$3$，右侧耗尽后接上 $4$。每次选出的较小首项不大于两侧所有剩余元素，所以输出前缀一直有序；这一不变量才是“合并正确”的理由。

每个元素在一次合并中仅被取走一次，故合并成本为 $\mathrm{\Theta }(n)$。对 $n$ 为二的幂，递归式 $T(n)=2T(n/2)+\mathrm{\Theta }(n)$ 的每层总工作为 $\mathrm{\Theta }(n)$，共有 $\mathrm{\Theta }(\log n)$ 层，得到 $\mathrm{\Theta }(n\log n)$；一般规模用上下取整划分，结论不变。二分搜索只保留一半候选，另一半根本不递归，因此 $T(n)=T(n/2)+O(1)$ 得 $O(\log n)$。拆出了两半不代表一定有两个递归调用。

快速排序的子问题大小依赖枢轴，若枢轴总取到极端值，会形成 $T(n)=T(n-1)+\mathrm{\Theta }(n)$ 的二次退化，说明“递归减小”不等于“平衡分治”，不能机械套用平衡分割递推。若子问题高度重叠，如朴素 Fibonacci 递归，记忆化比重复分治更合适。

分治用于排序、几何、FFT 与选择；平面最近点对理路平面最近点对Closest pair of points · Planar closest pair以分治和窄带 packing 证书在 O(n log n) 时间求 Euclidean 平面最近点对。展示了“递归解两侧 + packing 证明线性合并”的几何版本。折半搜索理路Meet-in-the-MiddleMeet-in-the-middle枚举两半指数状态并以排序或哈希匹配，用空间把枚举指数减半。把指数候选分成两半并在中间匹配，将典型 $2^n$ 枚举改成约 $2^{n/2}$ 的时间—空间权衡；它仍是 exact exponential 算法，不因“折半”变成多项式。

同一递归图像还能服务不同模型。对数方法动态化理路对数方法动态化logarithmic method · Bentley–Saxe dynamization把静态结构按二进制层级合并，从而以摊还重建代价支持插入。把静态结构按二进制块合并，以重建换取摊还更新；缓存无关模型理路缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。通过递归布局在未知 $B,M$ 下控制块传输；并行算法模型理路并行算法模型parallel algorithm model · parallel computation model用总工作、关键路径、处理器数和通信成本共同描述并行算法，而不只报告理想加速比。把相互独立的子问题同时执行，并分别分析工作与深度。这些成本可写成递归关系理路递推关系Recurrence relation用先前项规定序列当前项的关系。，再用主定理理路主定理Master theorem · Master method比较递归子问题总量与合并成本，快速求解一类分治递推式的渐近界。或递归树分析；动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。进一步处理子问题重叠带来的重复计算。