2.6 快速傅里叶变换

这一篇是第二卷的高潮：快速傅里叶变换（Fast Fourier Transform，FFT）。它把多项式乘法从 $O(n^2)$ 降到 $O(n\log n)$ ，是分治最辉煌的成就之一。FFT 的影响远超算法本身——它是数字信号处理、图像压缩、音频处理、大整数乘法的数学引擎，被《不列颠算法》列为 20 世纪十大算法之一。它的数学比前几篇重，但值得，因为理解了 FFT 你就理解了"换一个表示让计算变快"这个深刻思想。

1.起点：多项式乘法为什么慢

给两个 $n$ 次多项式 $A(x)=\sum_{i=0}^{n}a_ix^i$ 和 $B(x)=\sum_{i=0}^{n}b_ix^i$ ，求乘积 $C(x)=A(x)B(x)$ ，次数 $2n$ 。

朴素做法： $C_k=\sum_{i+j=k}a_ib_j$ 。每个系数 $C_k$ 是一个卷积，算所有 $2n+1$ 个系数，每个最多 $n+1$ 次乘法，总共 $O(n^2)$ 。

要加速，得换一个看多项式的视角。

2.多项式的两种表示

多项式有两种等价的表示：

系数表示： $(a_0, a_1, \dots, a_n)$ ——这是我们熟悉的。
点值表示：取 $d+1$ 个不同的点 $x_0,\dots,x_d$ （ $d$ 是次数），用这组点上的值 $(A(x_0),\dots,A(x_d))$ 表示。理由：一个 $d$ 次多项式被 $d+1$ 个点唯一确定。

关键洞察：在点值表示下，多项式乘法是 $O(n)$ 的！ 因为 $C(x_i)=A(x_i)\cdot B(x_i)$ ——在每个点上，乘积的值就是两个因子值的乘积，只需 $n$ 次点乘。这比系数表示下的 $O(n^2)$ 快得多。

于是策略出来了（这叫"插值乘法"）：

把 $A,B$ 从系数表示转成点值表示（求值，DFT）。
在点值表示下逐点相乘， $O(n)$ 得到 $C$ 的点值表示。
把 $C$ 从点值表示转回系数表示（插值，IDFT）。

如果这三步都高效，多项式乘法就快了。问题在于：第 1、3 步怎么做才快？ 朴素地在 $n$ 个点上求值，每个点 $O(n)$ ，总共还是 $O(n^2)$ ——白搭。FFT 的贡献，就是巧妙地选一组特殊点，让求值和插值都变成 $O(n\log n)$ 。

3.选哪组点：单位根

FFT 选的点是单位根（roots of unity）。 $n$ 次单位根是满足 $\omega^n=1$ 的复数 $\omega$ ，共 $n$ 个： $\omega^0,\omega^1,\dots,\omega^{n-1}$ ，其中 $\omega=e^{2\pi i/n}$ 。

n=8 的单位根，单位圆上均匀分布的 8 个点：
        ω⁰
   ω⁷ ●   ● ω¹
 ω⁶ ●  | |  ● ω²
   ω⁵ ●   ● ω³
        ω⁴

单位根有两个关键性质，是 FFT 加速的基石：

性质一（折半引理）： $\omega_{2n}^{2k}=\omega_n^k$ 。偶数幂的单位根等于规模减半的单位根。这让递归能把问题对半切。

性质二（消去引理）： $\omega_n^{k+n/2}=-\omega_n^k$ 。对称性——单位根前后半差一个负号。

4.FFT：分治求值 $O(n\log n)$

现在算 $A(\omega^0),A(\omega^1),\dots,A(\omega^{n-1})$ 。把 $A(x)$ 按奇偶拆成两半：

A(x)=A_{\text{even}}(x^2)+x\cdot A_{\text{odd}}(x^2)

其中 $A_{\text{even}}(y)=a_0+a_2y+\dots$ （偶次项）， $A_{\text{odd}}(y)=a_1+a_3y+\dots$ （奇次项）。它们都是 $\frac{n}{2}$ 次的多项式。

奇迹来了：在单位根上求值时， $x^2$ 把 $n$ 个不同的 $\omega^k$ 映射成只有 $\frac{n}{2}$ 个不同的值（因为折半引理 $\omega^{2k}=\omega_{n/2}^k$ ）。也就是说， $A_{\text{even}}$ 和 $A_{\text{odd}}$ 只需在 $\frac{n}{2}$ 个点上求值——子问题规模减半！

而且利用消去引理 $\omega^{k+n/2}=-\omega^k$ ：

A(\omega^{k+n/2})=A_{\text{even}}(\omega^{2k})-\omega^k\cdot A_{\text{odd}}(\omega^{2k})

和 $A(\omega^k)=A_{\text{even}}(\omega^{2k})+\omega^k\cdot A_{\text{odd}}(\omega^{2k})$ 只差一个符号——算一对 $(\omega^k, \omega^{k+n/2})$ 的值，复用同一对子结果，只需一次加一次减。

这就是 FFT 的蝶形结构：

FFT(A):
    if n == 1: return A        // 单点
    A_even = 偶次项, A_odd = 奇次项
    Y_even = FFT(A_even)       // 在 n/2 个点求值
    Y_odd  = FFT(A_odd)
    for k = 0 to n/2 - 1:
        Y[k]       = Y_even[k] + ωⁿᵏ · Y_odd[k]
        Y[k + n/2] = Y_even[k] - ωⁿᵏ · Y_odd[k]   // 蝶形
    return Y

递归关系 $T(n)=2T(n/2)+O(n)=O(n\log n)$ 。又一次和归并排序相同的递归、相同的解——分治的标志性结构。

5.插值：IDFT 也是 $O(n\log n)$

求值（DFT）把系数转点值，插值（IDFT）反过来。妙处是：IDFT 几乎和 DFT 一样，只是把单位根 $\omega$ 换成 $\omega^{-1}$ ，最后除以 $n$ 。所以插值也能用 FFT 同一套分治结构， $O(n\log n)$ 。

6.总复杂度： $O(n\log n)$ 的多项式乘法

把三步加起来：

求值（DFT） $A,B$ ：各 $O(n\log n)$ 。
点值相乘： $O(n)$ 。
插值（IDFT） $C$ ： $O(n\log n)$ 。

总共 $O(n\log n)$ 。从 $O(n^2)$ 到 $O(n\log n)$ ——和排序的 $O(n\log n)$ 同阶！ $n=10^6$ 时， $n^2=10^{12}$ 而 $n\log n\approx 2\times 10^7$ ，快了五万倍。这就是 FFT 的威力。

7.FFT 为什么这么重要

FFT 的应用铺天盖地：

信号处理：时域信号 $\leftrightarrow$ 频域频谱的转换（这就是"傅里叶变换"的本质——在频率空间看信号），音频/图像压缩（JPEG 用 DCT，MP3 用 MDCT，都是 FFT 的变种）。
大整数乘法：大数相乘本质是多项式乘法 + 进位，FFT 让它 $O(n\log n)$ ，Python 大整数乘法就这么实现。
卷积：任何能表达成卷积的运算（滤波、相关、多项式）都受益。
卷积神经网络：深度学习里某些高效卷积实现也用 FFT（深度学习课 3.3 节的卷积）。

它的核心思想——换一个表示（系数→点值/时域→频域），让计算从难变易——是一个普适的范式。第十一卷的"分解法"会把它提炼成通用设计工具。

8.练习

Q1. 为什么多项式乘法在"点值表示"下是 $O(n)$ ，而在"系数表示"下是 $O(n^2)$ ？

点值表示下，乘积 $C(x_i)=A(x_i)B(x_i)$ 在每个点是一次乘法， $n$ 个点共 $O(n)$ 。系数表示下， $C_k=\sum a_ib_j$ 是卷积，每个系数要扫一遍 $i+j=k$ ， $n$ 个系数共 $O(n^2)$ 。表示方式不同，乘法的代价天差地别——这正是"换表示让计算变快"的体现。

Q2. FFT 选单位根做求值点，是为了利用哪两个性质？它们怎么让递归规模减半？

折半引理 $\omega_{2n}^{2k}=\omega_n^k$ ：在单位根上求值时 $x^2$ 把 $n$ 个点压成 $n/2$ 个不同值，子问题（ $A_{\text{even}},A_{\text{odd}}$ ）规模减半。消去引理 $\omega^{k+n/2}=-\omega^k$ ：算一对 $(\omega^k,\omega^{k+n/2})$ 的值复用同一子结果，只差正负号。两者合起来让递归 $T(n)=2T(n/2)+O(n)=O(n\log n)$ 。

Q3.（思考题） FFT 的思想除了加速多项式乘法，还在哪些地方用上了"换一个表示让计算变易"？

信号处理：时域 $\to$ 频域（傅里叶变换），频域里滤波/压缩/特征提取更容易。大整数乘法：把数字当多项式系数，用 FFT 卷积。深度学习卷积：把空间域卷积转到频域（FFT）做逐点相乘。本质上都是"原表示下 $O(n^2)$ 的运算，换个表示（点值/频域）后变 $O(n)$ ，加上两次转换 $O(n\log n)$ 仍净赚"。这种"换表示"是普适设计范式，第十一卷会系统提炼。

9.小结

FFT 用单位根 + 分治，把多项式求值/插值压到 $O(n\log n)$ ，从而让多项式乘法从 $O(n^2)$ 降到 $O(n\log n)$ 。它的核心是"换表示（系数↔点值/时域↔频域）让计算变易"，这个思想远远超越多项式乘法本身，撑起了信号处理、压缩、大数乘法等一整片领域。下一篇是第二卷的收官，我们把第二卷所有分治算法提炼成一套设计法则。