FFT快离速散傅傅里里叶叶变变换换原及理其与快速算法算法优化解析

离散傅里叶变换的快速算法算是信号圈里的“老朋友”了，用得多，效率还高。尤其是数据量一大，用原始DFT计算真的是又慢又卡。FFT就不一样了，O(NlogN)的复杂度，性能提升肉眼可见。用在频谱、图像滤波这些场景，挺省心的。

FFT 的时间抽取法，思路上是把序列一分为二：奇数项、偶数项，各自再递归拆下去，合并。结构上常用的是蝶形运算，起来也比较直观，用图解的话更容易看懂。反过来的频率抽取法其实也是类似，只是分法从频域下手。两种方法配合使用，开发起来还挺灵活。

你如果做音频可视化、图像或者通信调制这些，FFT 基本是标配。推荐你看看下面几个资源： 蝶形运算图解和数字信号课件都挺清楚，讲得还不错。还有FFT 蝶形实现的例子，适合照着撸代码。

用的时候注意点，FFT 适合2 的幂次长度的数据，提前做个零填充是常规操作，别忘了哦。如果你用的是Python、Matlab、Web Audio API之类的环境，都有封装好的 FFT 库，直接调就行，省不少事。

如果你刚开始接触频域变换，建议从傅里叶变换原理这篇入手，搞懂了，再看各种变种也不会头大。