AnchorMathematics & Information › Signal Processing › Fourier Analysis › FFT
FFT
Fast Fourier Transform
快速傅里叶变换
一句话理解
FFT 是一类高效计算离散傅里叶变换（DFT）的算法。
DFT 定义答案，FFT 通过拆分并复用对称计算更快得到同一个答案。
最好理解的例子
分析一段录音包含哪些频率时，FFT 会通过拆分和复用计算，快速得到各频率分量。
核心机制
- 1
把 DFT 问题按奇偶位置或其他结构递归拆分。
- 2
复用旋转因子的周期性与对称性，避免重复计算。
- 3
以典型 O(N log N) 复杂度得到与直接 DFT 相同的频谱。
为什么重要
它把典型计算复杂度从 降到 ，使频谱分析、滤波和通信处理能够高效运行。
关键关系
快速对比
DFT 定义“要计算什么”；FFT 解决“怎样更快地计算它”。
常见误解
FFT 不是一种不同于 DFT 的新变换；在相同条件下，它计算的是同一个结果。
进一步理解
经典 radix-2 Cooley–Tukey 算法把偶数点与奇数点分开递归计算，因此最方便处理长度为 2 的幂的序列；其他长度也有相应算法。
知识邻域
Mathematics & Information → Signal Processing → Fourier Analysis