分治法

分治的核心不是“使用递归”本身，而是把实例拆成规模严格下降、结构相同且覆盖原问题的子问题，独立求解后再组合答案。真正决定效果的是三件事：子问题是否大致平衡、是否大量重叠、合并是否便宜；只要其中一项失控，递归写法未必带来效率。与动态规划相比，经典分治通常不复用重叠子问题。

归并排序把数组均分、递归排序两半，再线性合并，递归式 $T(n)=2T(n/2)+\mathrm{\Theta }(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在有限或良基的状态依赖上复用已计算结果的算法设计范式。则在子问题重叠时进一步共享状态。