案例库 · 工程与运营 · 技术决策 · 1965
库利-图基FFT把巨大的傅里叶计算变得廉价
1965年，库利和图基把变换分成偶数和奇数两半，把N²的工作量降到N log N。
IBM Research
那一手
离散傅里叶变换把一系列采样变成构成它们的频率，但直接计算意味着每个N个输出都要组合所有N个输入，所以工作量像N²一样增长。对于现实世界的信号，这太慢了，无法实时计算。
库利和图基发现，一个长度为N的变换可以干净地分成两个长度为N/2的变换，一个来自偶数索引的采样，一个来自奇数索引的采样，然后可以合并。重复这个分割会产生越来越小的变换，所以每个阶段处理所有N个采样一次，总共只有大约log2 N个阶段。
结果是，同样的数字以N log N的时间得出，而不是N²。论文中的例子设N=8,192，FFT在IBM 7094上大约5秒完成，而传统方法大约需要半小时，这个差距正是Wi-Fi、MP3和MRI能实时处理的原因。
为什么管用
- 一次分割把一个大变换变成两个一半大小的变换，每个都更便宜。
- 递归分割产生大约log2 N轮，每轮处理N个采样一次。
- 巨大的N²到N log N的下降把半小时的工作变成5秒。
值了多少把变换分成两半，重用较小的部分聪明
可以搬走什么
当计算以二次方增长时，寻找把它写成自身更小副本的方法；重用这些更小的答案把一个无望的问题变成微不足道的。
后来呢
库利-图基FFT成为现代数字信号处理的基础，用于运行Wi-Fi和移动网络，压缩音频为MP3，在MRI中重建图像，并支撑从地震学到肖尔算法背后的量子傅里叶变换的一切。
资料来源
发现哪里写错了？告诉我们。