CS170 · 第 3 讲

分治算法

以快速乘法、递推式、归并类算法与 FFT 为主线，掌握分解—递归—合并的设计范式。

---

学习目标

• 能默写分治算法的三步框架（分解、递归求解、合并），并说明真实工作量分别发生在哪三处
• 能由递归树推导整数乘法从 4T(n/2) 到 3T(n/2) 的常数改进如何在每层复合放大
• 能正确写出 Master 定理的三种情形，并对给定 a、b、d 判断 T(n) 的渐进复杂度
• 能解释随机选择算法中「好主元」的定义、出现概率为何是 1/2，以及为何期望时间为 O(n)
• 理解插值是求值的逆运算，并掌握逆 FFT 公式。
• 解释 FFT 矩阵各列的正交性及其如何导出反演公式。

先修回顾

• 大 O、Ω、Θ 符号与几何级数求和（首项决定递减、末项决定递增）
• 递归与递归树的基本画法
• 复数极坐标与单位根（用于第 2.6 节 FFT，本段末尾引入）
• 矩阵分块乘法与多项式求值
• FFT 算法与单位根求值。
• 复数运算、共轭与内积。

分治框架与整数乘法

分治（divide-and-conquer）策略把原问题按三步处理：

1. 分解：把规模为 n 的问题切成若干规模更小的同类型子问题；
2. 递归求解：对每个子问题递归调用自身；
3. 合并：把子问题的答案拼成原问题的答案。

真正的计算量分散在三处：把问题拆成子问题的过程、递归尾部规模足够小被直接求解的时刻、以及把部分答案黏合在一起的时刻。这三步由递归结构统一调度。

整数乘法（Multiply / Karatsuba 思想）

设 x、y 是两个 n 位二进制整数，n 为 2 的幂。把它们各切成左右两半：

\[x = 2^{n/2} x_L + x_R,\quad y = 2^{n/2} y_L + y_R.\]

直接展开得

\[xy = 2^{n} x_L y_L + 2^{n/2}(x_L y_R + x_R y_L) + x_R y_R.\]

若用 4 次 n/2 位乘法 \(x_L y_L,\; x_L y_R,\; x_R y_L,\; x_R y_R\)，得递推式

\[T(n) = 4T(n/2) + O(n),\]

解为 \(O(n^2)\)，与传统竖式乘法同阶，常数改进没有带来渐进收益。

高斯技巧把 4 次降为 3 次：只需计算

\[P_1 = x_L y_L,\quad P_2 = x_R y_R,\quad P_3 = (x_L + x_R)(y_L + y_R),\]

因为 \(x_L y_R + x_R y_L = P_3 - P_1 - P_2\)。新算法（图 2.1）递推式为

\[T(n) = 3T(n/2) + O(n).\]

递归树与 O(n^{log_2 3}) 的由来

递归树高 \(\log_2 n\)，分支因子 3，第 k 层有 \(3^k\) 个子问题，每个规模 \(n/2^k\)。该层工作量

\[3^k \cdot O\bigl(\frac{n}{2^k}\bigr) = \bigl(\frac{3}{2}\bigr)^k \cdot O(n).\]

层工作量随 k 以 3/2 等比递增，总工作量由末项主导：

\[O(3^{\log_2 n}) = O(n^{\log_2 3}) \approx O(n^{1.59}).\]

相比分支因子 4 时 \(4^{\log_2 n} = n^2\) 个叶子，常数系数的小改动在每一层复合放大，影响巨大。

实际实现一般不会递归到 1 位，而是到 16/32 位时交给硬件乘法指令。

Master 定理

分治算法常按「a 个规模为 n/b 的子问题 + O(n^d) 合并」的范式运行，运行时间满足

\[T(n) = aT(\lfloor n/b \rfloor) + O(n^d),\quad a>0,\; b>1,\; d \ge 0.\]

Master 定理给出闭式解：

\[T(n) = \begin{cases} O(n^d) & \text{if } d > \log_b a \\ O(n^d \log n) & \text{if } d = \log_b a \\ O(n^{\log_b a}) & \text{if } d < \log_b a \end{cases}\]

证明思路（递归树 + 几何级数）

假设 n 是 b 的幂以忽略下取整。递归树高 \(\log_b n\)，分支因子 a，第 k 层有 \(a^k\) 个规模 \(n/b^k\) 的子问题，该层工作量

\[a^k \cdot O\bigl((n/b^k)^d\bigr) = O(n^d) \cdot \bigl(a/b^d\bigr)^k.\]

层工作量构成等比数列，公比 \(r = a/b^d\)：

• \(r < 1\)（即 \(d > \log_b a\)）：递减级数，和由首项决定，为 \(O(n^d)\)；

• \(r > 1\)（即 \(d < \log_b a\)）：递增级数，和由末项决定。末项 k = \(\log_b n\) 时

\[O(n^d)\bigl(a/b^d\bigr)^{\log_b n} = a^{\log_b n} = n^{\log_b a};\]

• \(r = 1\)（即 \(d = \log_b a\)）：\(\log_b n\) 项都是 \(O(n^d)\)，得 \(O(n^d \log n)\)。

应用：二分查找

\(T(n) = T(\lfloor n/2 \rfloor) + O(1)\) 对应 \(a=1,\; b=2,\; d=0\)。\(\log_2 1 = 0 = d\)，属第二种情形，\(T(n) = O(\log n)\)。

归并排序

归并排序（Mergesort）是分治排序的标准实例：把数组对半切，递归排序两半，再合并两个有序子数组。

function mergesort(a[1..n])
    if n > 1:
        return merge(mergesort(a[1..⌊n/2⌋]), mergesort(a[⌊n/2⌋+1..n]))
    else: return a

合并子过程 merge(x[1..k], y[1..l]) 每次取两数组首元素较小者，递归构造结果。每次递归调用做 O(1) 工作，总时间 O(k + l)。于是

\[T(n) = 2T(n/2) + O(n) = O(n \log n).\]

迭代版本：维护一个队列 Q，初始把每个元素作为单元素有序数组 inject 进去；当 |Q| > 1 时，反复 eject 两个数组、merge 后 inject 回队尾，最终只剩一个有序数组。

function iterative-mergesort(a[1..n])
    Q = []
    for i = 1 to n: inject(Q, [a_i])
    while |Q| > 1: inject(Q, merge(eject(Q), eject(Q)))
    return eject(Q)

所有真实工作量都发生在 merge 阶段：从单元素开始两两合并成 2 元组，再成 4 元组，层层向上。

随机选择与中位数

中位数是列表的第 50 百分位。直接排序取中位需 \(O(n \log n)\)，但排序做了多余工作——我们只关心第 k 小的元素，不关心其余元素的相对顺序。

选择问题（Selection）：输入数集 S 与整数 k，输出 S 中第 k 小元素。中位数对应 \(k = \lfloor |S|/2 \rfloor\)。

随机分治算法

任选主元 v，把 S 分成三份：\(S_L\)（v）。三份可在 O(|S|) 时间内原地算出。然后

\[ \text{selection}(S,k) = \begin{cases} \text{selection}(S_L, k) & k \le |S_L| \\ v & |S_L| < k \le |S_L| + |S_v| \\ \text{selection}(S_R, k - |S_L| - |S_v|) & k > |S_L| + |S_v| \end{cases} \]

效率分析：好主元

称 v 为好主元（good pivot）若它落在 25%–75% 百分位之间。此时 \(|S_L|, |S_R| \le \frac{3}{4}|S|\)，子问题规模至少缩水四分之一。列表里恰有半数元素是好主元，故一次随机选到好主元的概率为 1/2。

由引理「平均抛 2 次公平硬币才出现一次正面」，平均两次 split 就能让数组缩到至多 3/4。设 T(n) 为期望运行时间：

\[T(n) \le T(3n/4) + O(n) \implies T(n) = O(n).\]

因此随机选择算法期望线性时间返回正确结果。最坏情况（每次都选到极值）是 \(\Theta(n^2)\)，但极罕见。

与 Mergesort 的对照：Mergesort 按位置对半切（不看元素大小），但花大力气 merge；选择算法精心按值划分，合并则无需额外工作。Quicksort 正是把选择算法的划分方式用于排序：划分后再递归两半即可，无需 merge。

插值与逆 FFT

插值（Interpolation）是求值（Evaluation）的逆运算：给定多项式 \(A(x)\) 在 \(n\) 个点 \(x_0, \ldots, x_{n-1}\) 上的取值，恢复其系数表示 \(a_0, \ldots, a_{n-1}\)。我们之前已设计出 FFT 算法，能在 \(O(n \log n)\) 时间内将系数表示转化为值表示——前提是求值点为 \(n\) 次单位根 \(1, \omega, \omega^2, \ldots, \omega^{n-1}\)。现在只需补上最后一块拼图。

令人惊异的是，插值可以通过同一个 FFT 算法完成，只需将原根 \(\omega\) 替换为 \(\omega^{-1}\)，再整体除以 \(n\)：

\[\langle \text{coefficients} \rangle = \frac{1}{n}\,\text{FFT}(\langle \text{values} \rangle; \omega^{-1})\]

至此，图 2.5 中的 \(O(n \log n)\) 多项式乘法算法已完全确定：

1. 求值：对 \(A\) 和 \(B\) 分别执行 FFT，得到它们在 \(n\) 次单位根处的值表示（\(O(n \log n)\)）。
2. 逐点相乘：对每个点 \(x_i\)，计算 \(C(x_i) = A(x_i) \cdot B(x_i)\)（\(O(n)\)）。
3. 插值：对 \(C\) 的值表示执行逆 FFT，恢复系数表示（\(O(n \log n)\)）。

总时间复杂度为 \(O(n \log n)\)。这一结果简洁得近乎巧合，但我们将在矩阵视角下看到其深刻原因。

矩阵解释与 Fourier 基

为了更清晰地理解插值，我们把多项式两种表示之间的关系写成矩阵形式。设 \(A(x)\) 是次数 \(\leq n-1\) 的多项式，其系数向量和值向量通过一个 \(n \times n\) 的 Vandermonde 矩阵 \(M\) 相联系：

\[\begin{pmatrix} A(x_0) \\ A(x_1) \\ \vdots \\ A(x_{n-1}) \end{pmatrix} = M \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{pmatrix}, \qquad M_{j,k} = x_j^k.\]

当 \(x_0, \ldots, x_{n-1}\) 互不相同时，\(M\) 可逆，因此插值就是乘以 \(M^{-1}\)。一般矩阵求逆需 \(O(n^3)\)，Vandermonde 矩阵可优化到 \(O(n^2)\)，但仍不够快。

在 FFT 的特殊情形下，取 \(x_j = \omega^j\)（\(\omega\) 为 \(n\) 次单位根），矩阵变为 \(M_n(\omega)\)，其 \((j, k)\) 元为 \(\omega^{jk}\)。关键性质是：\(M\) 的各列互相正交。取第 \(j\) 列与第 \(k\) 列的内积，得到等比数列求和：

\[1 + \omega^{j-k} + \omega^{2(j-k)} + \cdots + \omega^{(n-1)(j-k)}.\]

当 \(j \neq k\) 时，该和为 \((1-\omega^{n(j-k)})/(1-\omega^{j-k}) = 0\)；当 \(j = k\) 时每项都是 \(1\)，和为 \(n\)。由正交性得 \(MM^* = nI\)，因此 \(M^{-1} = (1/n)M^*\)。而 \(M^*\) 的 \((j, k)\) 元为 \(\omega^{-jk}\)，恰好等于 \(M_n(\omega^{-1})\) 的对应元，于是得到反演公式：

\[M_n(\omega)^{-1} = \frac{1}{n}\,M_n(\omega^{-1}).\]

几何上，FFT 是从标准基到 Fourier 基的一个旋转变换：求值将系数向量旋转到 Fourier 基下（值表示），插值将其旋转回标准基。多项式乘法在 Fourier 基下只是逐点相乘，远比标准基下简单。

Fast Fourier Transform 的递归算法

快速傅里叶变换（FFT）的核心是高效计算离散傅里叶变换（DFT），即计算向量 \(a = (a_0, \ldots, a_{n-1})\) 与 \(n \times n\) DFT 矩阵 \(M_n(\omega)\) 的乘积。矩阵 \(M_n(\omega)\) 的第 \((j,k)\) 项为 \(\omega^{jk}\)，其中 \(\omega\) 是主 \(n\) 次单位根，满足 \(\omega^n = 1\) 且 \(\omega^0, \omega^1, \ldots, \omega^{n-1}\) 互不相同。直接计算需要 \(O(n^2)\) 次运算。从多项式角度看，这等价于求多项式 \(A(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n-1}\) 在所有 \(n\) 次单位根处的取值，即求值问题。FFT 是多项式乘法算法的核心子程序。

分治结构。 将矩阵的列按奇偶分开后，利用 \(\omega^{n/2} = -1\) 和 \(\omega^n = 1\) 可发现：左上角的 \(n/2 \times n/2\) 子矩阵恰好是 \(M_{n/2}(\omega^2)\)，左下角的子矩阵同样如此。右上和右下子矩阵则分别是 \(M_{n/2}(\omega^2)\) 的第 \(j\) 行整体乘以 \(\omega^j\) 和 \(-\omega^j\)。因此，原先规模为 \(n\) 的矩阵-向量乘法可归约为两个规模为 \(n/2\) 的问题：分别计算 \(M_{n/2}(\omega^2)\) 与偶数下标系数 \((a_0, a_2, \ldots, a_{n-2})\) 和奇数下标系数 \((a_1, a_3, \ldots, a_{n-1})\) 的乘积。这一归约的关键在于 \(\omega^2\) 是 \(n/2\) 次本原单位根，因此子问题仍是合法的 DFT，可以递归求解。

递归算法。 这一分治策略直接导出图 2.9 的伪代码：当 \(\omega = 1\) 时直接返回输入（此时 \(M_1(1)\) 是单位矩阵）；否则对偶、奇子序列分别递归调用 FFT，参数变为 \(\omega^2\)；最后用蝶形（butterfly）操作合并结果：

\[ r_j = s_j + \omega^j s'_j, \quad r_{j+n/2} = s_j - \omega^j s'_j. \]

正确性。 由数学归纳法，基础情形 \(\omega=1\) 时 \(M_1(1)\) 是单位矩阵，显然正确。归纳步骤中，两个子调用分别正确计算了 \(M_{n/2}(\omega^2)\) 与对应子序列的乘积，而合并步骤恰好实现了分块矩阵乘法，因此整个算法正确计算了 \(M_n(\omega) a\)。

复杂度。 递归式为 \(T(n) = 2T(n/2) + O(n)\)，其中 \(O(n)\) 是合并阶段的 \(n/2\) 次复数乘法与加法。由主定理或递归树可得 \(T(n) = O(n \log n)\)，相比朴素的 \(O(n^2)\) DFT 实现了指数级加速。

递归展开与 FFT 电路

将 FFT 的递归完全展开，可得到一个由蝶形单元构成的电路，清晰暴露其并行结构。以 \(n=8\) 为例（图 2.10），电路具有如下关键性质：

1. 层次与规模。电路共有 \(\log_2 n\) 层，每层 \(n\) 个节点，总计 \(O(n \log n)\) 次运算。对于 \(n=8\)，有 3 层，每层 8 个节点，共 24 个运算节点。每个节点执行一次复数加法和一次复数乘法（蝶形操作）。从输入到输出，信号依次经过每一层的蝶形运算。

2. 输入的位逆序排列。输入顺序为 \(0, 4, 2, 6, 1, 5, 3, 7\)。这是因为递归顶层先取偶数下标、再取奇数下一层再对偶数组取其中偶数（即原数组中 4 的倍数），依此类推。换言之，输入按索引二进制表示的最低位递增排列，次低位次之。将自然二进制序 \(000, 001, 010, 011, 100, 101, 110, 111\) 的位反转，恰好得到 \(000, 100, 010, 110, 001, 101, 011, 111\)，即 \(0, 4, 2, 6, 1, 5, 3, 7\)。这种排列是递归按奇偶分组的直接结果，也是 FFT 实现中需要特别注意的地方。

3. 唯一路径。每个输入 \(a_j\) 到每个输出 \(A(\omega^k)\) 之间存在唯一路径。路径由 \(k\) 的二进制表示决定：从右（最低位）开始，0 走上边（0-边），1 走下边（1-边）。例如从 \(a_3\) 到 \(A(\omega^5)\)，\(k=5=101_2\)，路径为：最低位 1 走下边，中间位 0 走上边，最高位 1 走下边。反向路径（从输出到输入）则由 \(j\) 的二进制位决定。

4. 路径贡献。在 \(a_j\) 到 \(A(\omega^k)\) 的路径上，各边权值之和模 \(n\) 等于 \(jk\)。由于 \(\omega^n = 1\)，输入 \(a_j\) 对输出 \(A(\omega^k)\) 的贡献恰好是 \(a_j \omega^{jk}\)，与 DFT 定义一致，因此整个电路正确计算了多项式 \(A(x)\) 在所有 \(n\) 次单位根处的取值。这一性质是 FFT 电路正确性的核心保证。

5. 并行与硬件友好。电路中每层节点相互独立，天然适合并行计算和硬件实现。同一层的所有蝶形操作可以同时执行，因此理论上可用 \(\log_2 n\) 步完成全部计算。这使得 FFT 在 GPU 和 FPGA 上都能高效实现。

交互推演

递推树把每层代价与树高分开，适合在套公式前检查复杂度来源。

依据本地课程资料 lectures/chap2.pdf 重绘；交互用于解释算法状态与证明不变量，不替代正文中的完整论证。

常见误区

知识检查

本讲要点

• 分治三步：分解 → 递归求解 → 合并；真实工作量分布在拆分、递归尾部的平凡求解、以及答案的黏合三处
• 整数乘法通过高斯技巧把分支因子从 4 降到 3，使复杂度由 O(n²) 降到 O(n^{log₂ 3}) ≈ O(n^{1.59})；常数系数的改动在每层复合放大
• Master 定理三种情形取决于 d 与 \(\log_b a\) 的相对大小：首项主导（\(d > \log_b a\)）、叶子主导（\(d < \log_b a\)）、或每层等权（\(d = \log_b a\)）
• Mergesort 按位置对半切、花 O(n) merge，得 O(n log n)；随机选择按值划分、无需 merge，好主元概率 1/2，期望 O(n)
• 插值公式：⟨coefficients⟩ = (1/n) FFT(⟨values⟩; ω⁻¹)，时间复杂度 O(n log n)。
• 求值 = 乘以 Vandermonde 矩阵 M；插值 = 乘以 M⁻¹。
• FFT 矩阵 Mₙ(ω) 的各列正交，故 Mₙ(ω)⁻¹ = (1/n) Mₙ(ω⁻¹)。

一手资料

• lectures/chap2.pdf · 本段对应小节 · confidence: high · 第 55–57 节：复数乘法三积技巧、整数切半展开、递归树层工作量 (3/2)^k·O(n) 与叶子数 3^{log₂ n}
• lectures/chap2.pdf · 本段对应小节 · confidence: high · 第 58–60 节：T(n)=aT(⌊n/b⌋)+O(n^d) 的闭式解，公比 a/b^d 与 log_b a 比较
• lectures/chap2.pdf · 本段对应小节 · confidence: high · 第 60–62 节：mergesort 伪代码、merge 取首元素较小者、迭代版本用队列 eject/inject
• lectures/chap2.pdf · 本段对应小节 · confidence: high · 第 64–66 节：selection(S,k) 三向划分、好主元概率 1/2、T(n)≤T(3n/4)+O(n)⇒O(n)
• lectures/chap2.pdf · 2.6.3 Interpolation · confidence: high · Interpolation formula ⟨coefficients⟩ = (1/n) FFT(⟨values⟩; ω⁻¹) and the completion of the O(n log n) polynomial multiplication algorithm.
• lectures/chap2.pdf · 76-77 · confidence: high · Vandermonde matrix M relates coefficient and value representations; evaluation is multiplication by M, interpolation by M⁻¹.
• lectures/chap2.pdf · 77-78 · confidence: high · Orthogonality of FFT matrix columns; inversion formula Mₙ(ω)⁻¹ = (1/n) Mₙ(ω⁻¹); geometric view as rotation between standard and Fourier bases.
• lectures/chap2.pdf · 2.6.4 A closer look at the fast Fourier transform · confidence: high · 矩阵奇偶分块、图 2.9 伪代码、T(n) = 2T(n/2) + O(n) = O(n log n)
• lectures/chap2.pdf · 2.6.4 The fast Fourier transform unraveled · confidence: high · 蝶形结构、n=8 位逆序输入 0,4,2,6,1,5,3,7、路径贡献 a_j omega^{jk}