FFT：从公式到每秒百亿次

DFT 的账本：上一章说傅里叶变换把信号拆成频率分量。在电脑里它叫离散傅里叶变换（DFT）：N 个采样点，每个输出频率都要和全部 N 个点相乘再求和——总计算量约 N²。一百万点的音频就是万亿次乘法，六十年代的电脑要算上几天。

库利和图基的洞察：1965 年他们发现 DFT 里大量乘法是重复的——利用旋转因子的对称和周期性，可以把大 DFT 拆成小 DFT，小 DFT 再拆更小，像切蛋糕一样二分到不能再分，最后把结果按规律拼回来。计算量从 N² 降到 N·logN：一百万点从万亿次降到约两千万次，快了近十万倍。这就是 FFT。

一段公案：其实高斯在 1805 年手算小行星轨道时就用过同样的技巧，比傅里叶本人还早，只是写进了没人读懂的拉丁文笔记，直到 20 世纪才被翻出来。

为什么 N 爱取 2 的幂：二分拆分最顺的前提是点数能被一路整除，所以工程上常把信号补零凑到 1024、4096 这样的长度，FFT 跑得最快。

没有 FFT 就没有：4G/5G 的 OFDM 调制、实时频谱显示、MP3 编码、Wi-Fi、医学影像重建——全都建立在「变换足够快」之上。它被称为二十世纪最重要的算法之一，名副其实。

常见误区：FFT 不是一种新的变换，它就是 DFT 的快速算法——算出来的结果和 DFT 一模一样，只是快。

练一练：N=1024 时，DFT 约需 N² 次乘法，FFT 约需 N·log2N 次，各是多少？差多少倍？