形式陈述

分治算法把规模为 $n$$n$ 的实例分成若干严格更小的子实例，递归求解并合并结果。正确性通常由递归结构或强归纳证明；运行时间常满足

$$ T(n)=\sum_i T(n_i)+g(n). $$$$T(n)=\sum _{i}T(n_i)+g(n).$$

渐近记号和主定理是分析某些递推式的工具，不是理解分治策略形式陈述所必需的前置。

直觉

分治核心是子问题规模下降、覆盖原问题且答案可组合，而不是“使用递归”本身。

例子与边界

归并排序将数组分半、分别排序再线性归并；二分查找每次只保留一个半区。快速排序的子问题大小依赖枢轴，因此不能机械套用平衡分割递推。

推论与应用

分治用于排序、几何、FFT 和并行算法。设计时需分别证明分解覆盖、合并正确、递归终止和复杂度界。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005, Chs. 1–13。