分治法是计算机科学中的一种算法设计范式：将问题拆分为规模更小的实例，分别求解，再将结果组合成原问题的解。这一分解过程通常通过递归反复进行，直到剩余实例足够小，可以直接求解。其效率取决于子问题的构造方式，以及分解与合并所需的工作量。经典应用包括排序、查找和矩阵乘法。(introcs.cs.princeton.edu)
结构与正确性
分治算法通常包含三个阶段：
- 分解： 将当前问题实例拆分为规模更小的子问题。
- 求解： 递归求解这些子问题；达到基本情形时，则直接求解。
- 合并： 利用子问题的解，得到当前问题实例的答案。
各阶段的工作量不必相同。有些算法的大部分工作发生在分解阶段；另一些算法则需要耗费大量工作来合并结果。必须采用适当的规模度量，确保子问题的规模不断缩小，使递归调用最终到达基本情形。(ocw.mit.edu)
例如，归并排序将数组分为两半，分别排序，再合并排序结果。包含零个或一个元素的数组本身就已排好序。其正确性可以用数学归纳法来说明：基本情形是正确的，而合并两个已正确排序的较小数组，会得到一个正确排序的较大数组。这体现了递归结构与数学证明之间的联系。(introcs.cs.princeton.edu)
运行时间分析
分治算法的时间复杂度通常用递推关系描述。当每个问题实例产生 (a) 个规模约为 (n/b) 的子问题时，标准模型为
[ T(n)=aT(n/b)+f(n), ]
其中，(f(n)) 表示分解与合并所需的非递归工作量，而规模为常数的实例需要常数时间。这里的 (n) 必须表示适用的规模度量：例如，在方阵乘法中，它通常表示矩阵的阶数。(ocw.mit.edu)
递归树将递归调用表示为节点，并将各次调用的代价分布在不同层上。对于归并排序，两次处理半规模问题的调用，加上一次线性时间的合并，得到
[ T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n). ]
每一层的总工作量都是线性的，而层数是对数级的。这是利用渐近记号进行计算复杂性分析的一个例子，所用记号包括大O记号和表示紧确界的 (\Theta) 记号。(ocw.mit.edu)
主定理为这类递推关系中的若干重要类别提供了界。在常见的特殊情形 (f(n)=\Theta(n^d)) 下，通过比较 (d) 与 (\log_b a)，可以判断总代价主要由叶节点贡献、由各层均等贡献，还是由上层贡献。对于划分方式取决于输入的递推关系，例如快速排序中的递推关系，需要进一步分析，而不能直接代入这一等规模模型。(ocw.mit.edu)
代表性算法
排序。 快速排序围绕一个枢轴元素划分数组，再递归地对划分所得的各个区域排序。与归并排序不同，它的主要工作发生在递归调用之前，之后几乎不需要合并。均衡的划分能使递归高效进行，而反复出现极不均衡的划分，则可能导致平方级的运行时间。随机选择枢轴，或在开始时随机打乱数组，可以得到期望运行时间为 (O(n\log n)) 的随机化算法。(algs4.cs.princeton.edu)
查找。 二分查找将目标值与有序数组的中间元素比较，随后只在相关的一半中继续查找。其递推关系为 (T(n)=T(n/2)+\Theta(1))，因此运行时间为对数级。它常被视为只有一个子问题的分治法：与归并排序不同，它不会同时求解两半的问题。(ocw.mit.edu)
矩阵乘法。 斯特拉森算法将每个矩阵分为四块，通过递归计算七个分块乘积，而直接的分块乘法需要计算八个。加上额外的分块加减运算，得到
[ T(n)=7T(n/2)+\Theta(n^2), ]
因此，算术运算次数为 (\Theta(n^{\log_2 7}))，约为 (\Theta(n^{2.807}))。效率提升来自递归乘法次数的减少，而不只是对矩阵进行分块。(ocw.mit.edu)
傅里叶变换计算。 基二快速傅里叶变换将偶数索引和奇数索引的输入分开，形成两个规模减半的变换，再利用离散傅里叶变换的对称性质合并结果。当长度为二的幂时，这种方法需要 (\Theta(n\log n)) 次运算，而直接计算的代价为平方级。同样的分解也可以用多项式的偶数次项系数和奇数次项系数来描述。(introcs.cs.princeton.edu)
与动态规划的关系
分治法和动态规划都利用较小子问题的解来构造原问题的解。两者通常以如何处理重复计算来区分。经典的分治分解会产生相互独立的子问题实例；动态规划则通过保存并复用子问题的解来处理重叠子问题。记忆化在递归形式中实现了这种复用。这里的独立性指计算依赖关系上的独立，而不是概率意义上的独立。(ocw.mit.edu)
并行执行与实现
相互独立的递归调用可以并发执行，因此分治法是适用于并行计算的一种结构。并行性能既取决于总工作量，也取决于跨度，即存在依赖关系的操作所组成的最长链。即使一个计算过程包含许多递归任务，如果分解或合并阶段仍按顺序执行，其加速效果也可能有限。(cs.cmu.edu)
实际实现通常不会一直递归到最小的基本情形，而是在问题规模尚未缩小到这一程度时就停止递归，转用更简单的顺序执行方法。这可以减少函数调用或任务调度的开销；排序算法的实现可能对较小的子数组使用插入排序。划分是否均衡也很重要，因为不合理的划分会增加运行时间和递归深度。内存使用量取决于具体实现：数组归并排序通常需要辅助存储，而原地快速排序无需单独的划分数组，但仍需存储尚未完成的递归调用。(cs.cmu.edu)