快速傅里叶变换 FFTFast Fourier transform
将离散傅里叶变换分解为较小子变换，通过蝶形运算与旋转因子组合结果。
- 核心约束
- 子变换的顺序、指数符号与归一化约定必须与目标 DFT 一致。
- 适用问题
- 频谱分析、卷积和快速正交变换。
- 边界与取舍
- 长度因子、数据布局与数值精度影响实现；初始化和数据重排也有成本。
时间与空间#
N 为一维 DFT 长度；蝶形中的固定宽度浮点运算按常数成本。
- 时间复杂度
- 快速分解下 ；直接 DFT 为
- 辅助空间
- 常见实现 工作 / 旋转因子存储，原地变体不同
FFT 是一族 DFT 算法。基 2 Cooley–Tukey 需要 2 的幂长度；混合基、prime-factor、Rader 和 Bluestein 有不同分解条件。FFTW 可对任意长度使用 方法，但计划搜索时间另计，不能把此保证套给每个库的每个路径。
工程中的应用#
1 个案例 · 附源码FFmpeg 的 AAC 编码器通过 av_tx_init 取得 MDCT 函数。通用实现用折叠、旋转与半长 FFT 完成变换，FFT 再分解为较小子变换。
附源码片段 · 音视频处理
基础原理参考资料
Frigo & Johnson · FFTW3 design分解策略、任意长度 FFT、规划和机器相关实现。
FFmpeg 7.1 · Transform API变换类型、初始化计划和执行接口。