FFT · Cooley–Tukey

FFT：从 O(N²) 到 O(N log N)

DFT 的两层循环是 $O(N^2)$ 。1965 年 Cooley 与 Tukey（思想可追到高斯）发现一个分治结构，把它压到 $O(N \log N)$ ——这就是快速傅里叶变换 FFT。它让实时音频、数字通信、图像压缩成为可能，常被列为20 世纪最重要的算法之一。

1 · 核心：奇偶分解

把 N 点 DFT 按下标的奇 / 偶拆成两个 N/2 点 DFT，再用一个「旋转因子 twiddle factor」 $W_n^k = e^(-i2\pi k/N)$ 合并：

X[k] = E[k] + Wₙᵏ·O[k] | X[k+N/2] = E[k] − Wₙᵏ·O[k]

E 是偶下标样本的 DFT、O 是奇下标的。一次乘加同时算出相距 N/2 的两个输出——这就是「蝶形 butterfly」。每个子问题再这样二分下去，深度 $\log _2N$ 层、每层 N 次运算，合计 $O(N \log N)$ 。

下图是 N = 8 的完整蝶形网络（迭代版，自底向上）。最左列是输入，但顺序被位反转 bit-reversal 打乱了（这样后面每次蝶形都正好取相邻/等距的对）；往右每一列 = 一个 stage。按「下一蝶形 ▸」逐个看 a' = a + W·b / b' = a − W·b 怎样就地改写两个值。

位反转为什么必要？ 递归地「先偶后奇」分组，等价于把每个下标的二进制位左右翻转后排序： ${0,1,2,\dots ,7}$ → 0,4,2,6,1,5,3,7。这么一摆，迭代版每个蝶形要配对的两个元素永远相邻或等距，就能原地 in-place 完成、不需要额外数组。

到底快多少？ $N \log _2N$ 对 $N^2$ :N=8 是 24 对 64;N=1024 是 ~1 万对 ~100 万（快 100×）;N=100 万是 ~2000 万对 ~1 万亿（快 5 万×）。正是这条曲线的差距，把「频域」从理论搬进了你每天用的耳机、Wi-Fi 和相机。