快速傅里叶变换 快速傅里叶变换英語Fast Fourier Transform FFT是快速计算序列的离散傅里叶变换DFT或其逆变换的方法傅里叶分析将信号从原始域通常是时间或空间转换到頻域的表示或者逆过来转换FFT会通过把DFT矩阵分解为稀疏大多为零因子之积来快速计算此类变换 因此它能够将计算DFT的复杂度从只用DFT定义计算需要的 O  n   displaystyle On 降低到 O  n log  n  displaystyle Onlog n 其中 n displaystyle n 为数据大小 快速傅里叶变换广泛的应用于工程科学和数学领域这里的基本思想在年才得到普及但早在年就已推导出来 年美國數學家吉爾伯特斯特朗把FFT描述为我们一生中最重要的数值算法它还被IEEE科学与工程计算期刊列入世纪十大算法