分治

分治是三个字：拆（分成独立子问题）、解（递归解决）、合（合并结果）。它是最早被系统化的设计范式，也是与并行计算（→ 并发与同步）天然契合的范式。本章讲适用条件、经典问题与复杂度分析。

适用条件

分治的前提是子问题独立——子问题之间不共享需要协调的状态。子问题重叠时（同一个子问题被反复求解），分治会重复劳动，此时应转向动态规划（→ 动态规划）。这个判断是范式选择的分水岭：

归并排序：左半与右半独立 → 分治；
斐波那契： $F(n-1)$ 与 $F(n-2)$ 共享 $F(n-3)$ 等子问题 → 动态规划。

代价写成递归式 $T(n) = aT(n/b) + f(n)$ ，用主定理求解——分治的分析几乎总是一行主定理。

经典问题

归并排序

$T(n) = 2T(n/2) + O(n)$ → $O(n \log n)$ 。分治的原型：拆分平凡、合并线性、子问题独立。

快速幂

x^n = \begin{cases} (x^{n/2})^2 & n \text{ 偶} \\ x \cdot (x^{(n-1)/2})^2 & n \text{ 奇} \end{cases}

从 $O(n)$ 次乘法降到 $O(\log n)$ 次——分治思想在"幂运算"上的一行实现，也是矩阵快速幂（ $O(\log n)$ 求斐波那契）的基础。

Karatsuba 乘法

两个 $n$ 位数相乘，朴素是 $O(n^2)$ （每位与每位相乘）。Karatsuba 把数分两半 $x = x_1 B^{m} + x_0$ ，利用恒等式

x_1 y_0 + x_0 y_1 = (x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0

把 3 次半长乘法（而非 4 次）搞定， $T(n) = 3T(n/2) + O(n)$ → $O(n^{\log_2 3}) \approx O(n^{1.585})$ ——分治把乘法从 $O(n^2)$ 降到 $O(n^{1.585})$ ，思想后来推广到 Strassen 矩阵乘法（ $O(n^{2.81})$ ）与更快的渐近算法。

与并行计算的契合

分治的子问题独立，天然并行：递归树的不同分支可以分给不同核（fork-join 模型，Java ForkJoinPool、Cilk）。归并排序的并行版本在 $P$ 个核上 $O(n \log n / P + \log P)$ 。分治是并行算法的原型范式——比数据依赖强的算法（如某些 DP）难并行得多。

本章要点

分治三步：拆、解、合；子问题必须独立，重叠时考虑动态规划
代价 $T(n) = aT(n/b) + f(n)$ ，一行主定理
Karatsuba 把乘法从 $O(n^2)$ 降到 $O(n^{1.585})$ ；Strassen 推广到矩阵
合并阶段的技巧（分界带、三数取中）常是算法快慢的关键
子问题独立使分治天然并行，是 fork-join 模型的原型

分治