快速傅里叶变换

快速傅里叶变换（英语：Fast Fourier Transform, FFT），是计算序列的离散傅里叶变换（DFT）或其逆变换的一种算法。傅里叶分析将信号从原始域（通常是时间或空间）转换到频域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏（大多为零）因子之积来快速计算此类变换。 因此，它能够将计算DFT的复杂度从只用DFT定义计算需要的 O ( n 2 ) {\displaystyle O(n^{2})} ，降低到 O ( n log ⁡ n ) {\displaystyle O(n\log n)} ，其中 n {\displaystyle n} 为数据大小。

快速傅立叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及，但早在1805年就已推导出来。 1994年吉尔伯特·斯特朗（英语：Gilbert Strang）把FFT描述为“我们一生中最重要的数值算法”，它还被IEEE科学与工程计算期刊列入20世纪十大算法。