分治算法

1. 概述与学习目标

1.1 什么是分治算法

分治算法（Divide and Conquer）是一类将大问题分解为若干规模较小、结构相同的子问题，递归求解后合并结果的算法设计策略。Thomas H. Cormen 等在《Introduction to Algorithms》（CLRS）第 4 章将分治形式化为三步范式：

1. 分解（Divide）：将原问题划分为 $a$ 个规模为 $n/b$ 的子问题；
2. 解决（Conquer）：递归求解各子问题；若子问题足够小（达到基线阈值 $n_0$）则直接求解；
3. 合并（Combine）：将子问题的解合并为原问题的解。

分治算法的时间复杂度由递推关系刻画：

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

其中 $a \geq 1$ 为子问题数，$b > 1$ 为规模缩减比，$f(n)$ 为分解与合并的总代价。主定理（Master Theorem, Bentley-Haken-Saxe 1980）给出此递推的通用解法，分三种情况对应不同的渐近量级。

分治算法分类树：
                          分治算法
                              |
        ┌─────────┬───────────┴──────────┬────────────┐
     排序分治    代数分治              几何分治        信号分治
        │          │                     │                │
   ┌────┴───┐  ┌───┴────┐          ┌────┴────┐      ┌────┴────┐
  归并排序 快排 Karatsuba Strassen  最近点对  最大子数组  FFT  数论变换
  von Neu. Hoare 1963     1969      1976     1976    1965     NTT
  1945    1961  O(n^1.585) O(n^2.807) O(nlogn) O(nlogn) O(nlogn)

分治与其他算法策略的本质区别：

一句话定义：分治 = Divide（分解 $a$ 个 $n/b$ 子问题）+ Conquer（递归求解）+ Combine（合并结果）；复杂度由 $T(n) = aT(n/b) + f(n)$ + 主定理刻画；归并 $O(n \log n)$、快排 $O(n \log n)$ 平均、Karatsuba $O(n^{1.585})$、Strassen $O(n^{2.807})$、FFT $O(n \log n)$、最近点对 $O(n \log n)$ 是六大经典分治算法。

1.2 学习目标

完成本文档学习后，你将能够：

1. 记忆归并排序 $O(n \log n)$、快速排序 $O(n \log n)$ 平均/$O(n^2)$ 最坏、二分查找 $O(\log n)$、Karatsuba $O(n^{\log_2 3}) \approx O(n^{1.585})$、Strassen $O(n^{\log_2 7}) \approx O(n^{2.807})$、FFT $O(n \log n)$、最近点对 $O(n \log n)$ 的形式化复杂度，复述主定理三种情况的形式化条件；
2. 理解 von Neumann 1945 EDVAC 报告归并排序（IEEE Annals of the History of Computing 15(4):27-75 1993 重印）、Hoare 1961-1962 CACM 4(7):321 与 Computer Journal 5(1):10-15 快速排序、Karatsuba-Ofman 1963 Soviet Physics-Doklady 7:595-596 大整数乘法（颠覆 Kolmogorov $O(n^2)$ 猜想）、Cooley-Tukey 1965 Mathematics of Computation 19:297-301 FFT、Strassen 1969 Numerische Mathematik 13(4):354-356 矩阵乘法（首次突破 $O(n^3)$）、Bentley-Haken-Saxe 1980 SIGACT News 12(3):36-44 主定理的历史脉络，说明各分治算法的设计动机；
3. 应用归并排序（自顶向下/自底向上）、快速排序（Lomuto/Hoare/三路/随机化/双轴）、Karatsuba 大整数乘法、Strassen 矩阵乘法、Cooley-Tukey FFT（递归/迭代蝶形）、最近点对（分治+strip）编写可运行的 Python/C++/Java 代码，解决 LeetCode 53、169、23、148、240、315、973 等高频问题；
4. 分析主定理三种情况的形式化条件（$f(n) = O(n^{\log_b a - \epsilon})$ / $\Theta(n^{\log_b a} \log^k n)$ / $\Omega(n^{\log_b a + \epsilon})$）与正则条件、递归树分析法、Karatsuba 三乘法替代四乘法的代数恒等式、Strassen 七乘法替代八乘法的代数恒等式、Cooley-Tukey 蝶形运算的对称性利用、最近点对 strip 检查的 $O(1)$ 摊还分析，掌握”递归树归约、代数恒等式、势能摊还”三大核心论证方法；
5. 评估各分治算法在”分解均匀性”、“合并成本”、“递归深度”、“基线阈值”、“并行化难度”维度上的优劣，识别 NumPy/BLAS Strassen 矩阵乘法、FFTW 库、Python Timsort 归并段、PostgreSQL 外部归并排序、MapReduce 分布式排序、GPU 并行 FFT 的选型动机；
6. 对比归并、快排、Karatsuba、Strassen、FFT、最近点对在递推关系、子问题数 $a$、子问题规模 $n/b$、合并代价 $f(n)$、总复杂度、并行性维度的差异；
7. 创造性设计基于分治的开源项目解决方案，如 MapReduce 分布式词频统计、CUDA FFT 卷积神经网络、PostgreSQL 多路外排序、Go goroutine 并行归并、Karatsuba RSA 大数运算、Strassen BLAS 加速、最近点对地理 LBS 服务。

1.3 术语表

1.4 全景对比表

2. 历史动机与演进

2.1 时间线

timeline
    title 分治算法八十年演进史
    1805 : Gauss 私人手稿发现 FFT 思想（被埋没 160 年）
    1945 : von Neumann EDVAC 报告首述归并排序
    1960 : Karatsuba 莫斯科大学研讨会颠覆 Kolmogorov O(n²) 猜想
    1961 : Hoare CACM 发表快速排序 Algorithm 64
    1963 : Karatsuba-Ofman 苏联科学院院报英译版 7:595-596
    1965 : Cooley-Tukey Mathematics of Computation 19:297-301 FFT
    1969 : Strassen Numerische Mathematik 13(4):354-356 矩阵乘法
    1976 : Bentley-Shamos STOC 最近点对 O(n log n)
    1980 : Bentley-Haken-Saxe SIGACT News 主定理系统化
    1990 : Coppersmith-Winograd O(n^2.376) 矩阵乘法
    2005 : FFTW3 库生产级 FFT 实现
    2012 : Vassilevska Williams STOC O(n^2.3727)
    2019 : Harvey-van der Hoeven 大整数乘法 O(n log n)
    2021 : Alman-Williams SODA O(n^2.3728596)

2.2 关键人物与设计决策

John von Neumann（1903-1957）：匈牙利裔美籍数学家。1945 年为 EDVAC 计算机撰写《First Draft of a Report on the EDVAC》时，首次书面描述了归并排序。这一设计展示了存储程序计算机的强大能力：可以在内存中按 $O(n \log n)$ 排序数据，远优于当时占主导的 $O(n^2)$ 排序。Knuth 在 TAOCP Vol.3 §5.2.4 详细考据此事。归并排序是分治思想的最早系统化应用。

Anatolii Alexeevich Karatsuba（1937-2008）：苏联数学家。1960 年莫斯科大学研讨会上，Andrey Kolmogorov 提出”$O(n^2)$ 是大整数乘法的下界”猜想，并让全班学生尝试证明。23 岁的 Karatsuba 一周后发现 $O(n^{\log_2 3}) \approx O(n^{1.585})$ 算法，颠覆了 Kolmogorov 的猜想。Kolmogorov 震惊之余，亲自将 Karatsuba 的结果写成论文发表于《Soviet Physics-Doklady》1963 年 7(7):595-596（署名 Karatsuba-Ofman）。这是分治算法突破”朴素下界”的开山之作。

James W. Cooley（1926-2016）与 John W. Tukey（1915-2000）：1965 年 IBM Watson 研究中心与 Princeton 大学。Cooley 在 Richard Garwin 的建议下与 Tukey 合作，将 Tukey 早期关于 Fourier 分析的洞察实现为系统算法。论文《An algorithm for the machine calculation of complex Fourier series》发表于 Mathematics of Computation 19:297-301，仅 4 页。FFT 将 DFT 从 $O(n^2)$ 降到 $O(n \log n)$，被誉为 20 世纪最重要的算法之一，开启了数字信号处理学科。Heideman-Johnson-Burrus 1984 考据发现 Gauss 在 1805 年私人手稿中已有同样思想（早 160 年）。

Volker Strassen（1936-）：德国数学家。1969 年在《Gaussian Elimination is not Optimal》Numerische Mathematik 13(4):354-356 提出用 7 次乘法替代朴素 $2 \times 2$ 矩阵乘法的 8 次乘法，复杂度 $O(n^{\log_2 7}) \approx O(n^{2.807})$，首次突破 $O(n^3)$ 矩阵乘法。Strassen 的洞察在于：用额外的加法代替乘法（在加法比乘法便宜的代数结构上获益）。后续 Coppersmith-Winograd 1990 $O(n^{2.376})$、Williams 2012 $O(n^{2.3727})$、Alman-Williams 2021 $O(n^{2.3728596})$ 沿此路线不断改进。

Jon L. Bentley、Dorothea Haken、James B. Saxe：1980 年在《A general method for solving divide-and-conquer recurrences》SIGACT News 12(3):36-44 系统化主定理。该文给出 $T(n) = aT(n/b) + f(n)$ 的通用解法，按 $f(n)$ 与 $n^{\log_b a}$ 的渐近比较分三种情况。Cormen-Leiserson-Rivest《CLRS》1990 第一版将此法命名为”Master Theorem”，成为算法分析的标准工具。

关键设计决策：

1. 三步范式标准化（von Neumann 1945）：将分治明确为 Divide-Conquer-Combine 三步骤，每步独立分析；
2. 递推关系刻画复杂度（Bentley-Haken-Saxe 1980）：用 $T(n) = aT(n/b) + f(n)$ 统一描述分治复杂度；
3. 代数恒等式减少子问题数（Karatsuba 1960、Strassen 1969）：通过引入额外加减法减少乘法次数，本质是利用代数结构；
4. 对称性利用（Cooley-Tukey 1965）：FFT 利用单位根的对称性 $\omega_N^{k+N/2} = -\omega_N^k$，将 DFT 分解为两个半长 DFT；
5. 摊还分析合并成本（Bentley-Shamos 1976）：最近点对 strip 检查中，每个点只需检查 7 个邻居，整体 $O(n)$ 合并。

3. 形式化定义与主定理

3.1 分治三步范式

定义 3.1（分治算法）：分治算法是求解问题 $P$ 的算法 $A$，由三元组 $(\text{Divide}, \text{Conquer}, \text{Combine})$ 构成：

1. Divide：将原问题 $P_n$（规模 $n$）划分为 $a$ 个规模为 $n/b$ 的子问题 $P_{n/b}^{(1)}, P_{n/b}^{(2)}, \ldots, P_{n/b}^{(a)}$，划分代价 $D(n)$；
2. Conquer：递归调用 $A$ 求解各子问题；若 $n \leq n_0$（基线阈值）则直接求解，代价 $\Theta(1)$；
3. Combine：将子问题解 $s_1, s_2, \ldots, s_a$ 合并为原问题解 $s$，合并代价 $C(n)$。

总递推关系：

$T(n) = \begin{cases} \Theta(1) & n \leq n_0 \\ aT(n/b) + D(n) + C(n) & n > n_0 \end{cases}$

合并 $D(n) + C(n)$ 记为 $f(n)$，得标准形式 $T(n) = aT(n/b) + f(n)$。

3.2 主定理（Master Theorem）

定理 3.1（主定理，Bentley-Haken-Saxe 1980）：设 $a \geq 1$、$b > 1$ 为常数，$f(n)$ 为渐近非负函数，递推关系 $T(n) = aT(n/b) + f(n)$ 的解分三种情况：

• 情况 1：若 $f(n) = O(n^{\log_b a - \epsilon})$ 对某常数 $\epsilon > 0$ 成立，则 $T(n) = \Theta(n^{\log_b a})$；
• 情况 2：若 $f(n) = \Theta(n^{\log_b a} \log^k n)$ 对某 $k \geq 0$ 成立，则 $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$；
• 情况 3：若 $f(n) = \Omega(n^{\log_b a + \epsilon})$ 对某常数 $\epsilon > 0$ 成立，且正则条件 $af(n/b) \leq cf(n)$ 对某常数 $c < 1$ 与所有充分大 $n$ 成立，则 $T(n) = \Theta(f(n))$。

证明（递归树法）：

构造递归树：根节点贡献 $f(n)$，第 $i$ 层有 $a^i$ 个节点，每个节点贡献 $f(n/b^i)$。故第 $i$ 层总贡献 $a^i f(n/b^i)$。树高 $\log_b n$，叶节点数 $a^{\log_b n} = n^{\log_b a}$，每个叶节点贡献 $\Theta(1)$，故叶层总贡献 $\Theta(n^{\log_b a})$。

总复杂度：

$T(n) = \sum_{i=0}^{\log_b n - 1} a^i f(n/b^i) + \Theta(n^{\log_b a})$

令 $g(i) = a^i f(n/b^i)$，分析其随 $i$ 的单调性：

• 情况 1：$f(n) = O(n^{\log_b a - \epsilon})$，则 $g(i) = a^i \cdot O((n/b^i)^{\log_b a - \epsilon}) = O(n^{\log_b a - \epsilon} \cdot a^i / b^{i(\log_b a - \epsilon)}) = O(n^{\log_b a - \epsilon} \cdot a^i / (a^i \cdot b^{-i\epsilon})) = O(n^{\log_b a - \epsilon} \cdot b^{i\epsilon})$。随 $i$ 增大 $g(i)$ 几何级数递减，但叶层 $n^{\log_b a}$ 项占主导，故 $T(n) = \Theta(n^{\log_b a})$。

• 情况 2：$f(n) = \Theta(n^{\log_b a} \log^k n)$，则 $g(i) = a^i \cdot \Theta((n/b^i)^{\log_b a} \log^k(n/b^i)) = \Theta(n^{\log_b a} (\log n - i \log b)^k)$。每层贡献 $\Theta(n^{\log_b a} (\log n - i \log b)^k)$，从 $i=0$ 到 $\log_b n$ 求和为 $\Theta(n^{\log_b a} \log^{k+1} n)$。

• 情况 3：$f(n) = \Omega(n^{\log_b a + \epsilon})$ 且正则条件 $af(n/b) \leq cf(n)$（$c < 1$），则 $g(i) \leq c^i f(n)$，几何级数递减，根层 $f(n)$ 占主导，故 $T(n) = \Theta(f(n))$。

$\square$

应用示例：

注：二分查找 $T(n) = T(n/2) + O(1)$，$a=1, b=2, \log_b a = 0$，$f(n) = O(1) = \Theta(n^0 \log^0 n)$，属情况 2 ($k=0$)，故 $T(n) = \Theta(\log n)$。

3.3 代数恒等式与子问题数缩减

分治算法优化的核心是减少子问题数 $a$，关键在于代数恒等式。

Karatsuba 恒等式（1960）：设 $x = a \cdot 10^m + b$、$y = c \cdot 10^m + d$，则

$xy = ac \cdot 10^{2m} + [(a+b)(c+d) - ac - bd] \cdot 10^m + bd$

朴素乘法需 4 次子乘法 $ac, ad, bc, bd$，Karatsuba 用 $(a+b)(c+d)$ 一次乘法代替 $ad + bc$ 两次乘法，总乘法次数 $3$ 次，故 $a = 3$、$T(n) = 3T(n/2) + O(n) = \Theta(n^{\log_2 3})$。

Strassen 恒等式（1969）：设 $2 \times 2$ 矩阵乘法 $C = AB$，朴素需 8 次子矩阵乘法。Strassen 定义 7 个中间量：