分治法

分治法（Divide and Conquer）的核心逻辑很直接：把大问题拆成若干个小一号的同构子问题，独立解决后，再将结果合并。

三个关键步骤

1. 分解（Divide）： 明确子问题的定义，并确保子问题的规模严格小于原问题。
2. 求解（Conquer）： 处理递归基（Base Case），并对每个子问题递归调用。
3. 合并（Combine）： 将子问题的解组装成原问题的解，并评估这一步的时间开销。

典型的时间复杂度递推式如下：

$$T(n)=aT(n/b)+f(n),$$

其中 $a$ 代表子问题的数量，每个子问题的规模约为 $n/b$，$f(n)$ 则涵盖了划分和合并所需的额外开销。对于这类递推式，通常可以使用递归树法、代入法或主定理（Master Theorem）来求解。如果子问题规模不规则或存在复杂依赖，可能需要其他分析手段。

经典案例

• 归并排序：将数组一分为二递归排序，最后线性合并，总复杂度 $\Theta(n\log n)$。
• 快速排序：线性划分（Partition）后，子问题的大小取决于输入数据的分布。
• 二分搜索：每次排除一半范围，仅有一个子问题，合并开销为常数级。
• 最近点对问题与 Karatsuba 乘法：这类问题的突破点往往在于如何优化“合并”策略，从而避免暴力枚举。

注意：单纯把算法拆开并不会自动提升性能。子问题的解加上合并步骤必须能正确还原原问题的解，且最终的递推式复杂度必须优于原算法。

与动态规划的区别

分治法的子问题通常是相互独立的。如果子问题之间存在大量重叠，就会重复计算，适合考虑记忆化搜索或动态规划（DP）。

反之，虽然两者都常用递归实现，但代码语法本身不能决定算法的设计范式。

虽然独立的子问题分支可以并行执行，但实际加速比受限于关键路径长度、合并开销、任务调度、通信延迟以及内存访问瓶颈。

一个完整的递推论证

对八个元素归并排序，子问题规模依次为一个 8、两个 4、四个 2，最后是八个规模为 1 的基本情况。三层合并中，每层总共处理八个元素。在简化模型 $T(1)=1$、$T(n)=2T(n/2)+n$ 下，得到 $T(2)=4$、$T(4)=12$、$T(8)=32$。这些是模型工作单位，不是精确比较次数或耗时。

一般地，若 $n=2^k$，每层合并成本为 $n$，共有 $k$ 层和 $n$ 个叶子，所以 $T(n)=n\log_2 n+n$。正确性要另做归纳：规模为零或一的段已有序；若两个子结果都有序，每次取较小首元素，就能得到两者并集的有序排列。子问题严格变小保证终止。仅有递推式或仅能终止，都不能证明输出正确。

主定理何时适用

对 $T(n)=aT(n/b)+f(n)$，假定 $a\geq1$、$b>1$ 为常数，合并成本非负，基本情况为常数成本。令 $p=\log_b a$，比较 $f(n)$ 与 $n^p$。常用形式为：

• 若存在 $\varepsilon>0$ 使 $f(n)=O(n^{p-\varepsilon})$，则 $T(n)=\Theta(n^p)$。
• 若 $f(n)=\Theta(n^p)$，则 $T(n)=\Theta(n^p\log n)$。
• 若存在 $\varepsilon>0$ 使 $f(n)=\Omega(n^{p+\varepsilon})$，且最终满足 $a f(n/b)\leq c f(n)$，其中常数 $c<1$，则 $T(n)=\Theta(f(n))$。

这些是充分条件，不涵盖所有递推式。归并排序属于中间情况；二分搜索的 $a=1$、$b=2$、$f(n)=\Theta(1)$，得到 $\Theta(\log n)$。由于只求解一个更小问题，二分搜索也常归为减治。快速排序的任意枢轴会产生不等长分支，因此不能直接用该定理分析其最坏情况。分支独立允许并行，但不会消除合并成本。

参考来源

• MIT OpenCourseWare: Divide and Conquer

我的阅读 · 打开过的笔记会记在当前浏览器里。