1周学FFT——第3天 DFT算法的时间消耗和快速傅里叶变换

考虑DFT的运算公式为：

根据上式，可得的展开式为：

其中。

如果根据DFT的展开式直接编写算法的话，所需的运算次数估算如下：

由于是复数，所以要计算1个需要进行N次复数乘法，和N-1次复数加法。更进一步，计算N点的DFT则需要次复数乘法和次复数加法。

而1次复数乘法需要分为4次实数乘法和2次实数加法（也可以是2次乘法，2次乘加），1次复数加法需要分为2次实数加法。所以计算1个需要进行4N次实数乘法，2N+2(N-1)次实数加法。更进一步，计算N点DFT需要次实数乘法，次实数加法，即计算N点DFT需要的运算次数与成正比。

由于1次运算需要消耗1个或几个时钟周期，所以可以用运算次数来衡量算法的时间消耗。所以通过上面的分析可知DFT算法的时间消耗与成正比。

虽然绝大多数现代CPU、GPU、DSP中都实现了乘加指令（MAC或FMAC），可以有效减少加法运算次数，但仍改变不了DFT算法的时间消耗与成正比的结论。

在计算机科学当中，这一结论也被称为“DFT算法的时间复杂度为”。这说明DFT算法消耗的时间会随着N的增加呈J型曲线增长。另外，由于IDFT与DFT运算结构基本一致，所以IDFT算法的时间消耗和DFT算法的时间消耗基本相当。这意味着几乎所有的数字信号处理的算法只有理论上的价值，是无法实用的。

好在科学家们发明了FFT。

快速傅里叶变换（FFT）并不是一种新的变换，它是离散傅里叶变换（DFT）的一种快速算法。

DFT在数字信号处理领域中占有极为重要的地位，它是对离散信号进行频谱分析的有力（唯一）工具。但是，由于DFT算法的时间复杂度为，导致它在相当长时间里并没有得到真正的应用。直到1965年，J. W. Cooley和J. W. Tukey发表了著名的论文“An Algorithm for the Machine Calculation of Complex Fourier Series”，提出了DFT的一种快速算法，情况才发生了根本的改变。之后，又出现了各种各样计算DFT的方法，这些方法统称为快速傅里叶变换（Fast Fourier Transformer），简称FFT[从玉良，2009，p87]。

FFT算法极大的简化了DFT的时间消耗，一般可缩短1～2个数量级，从而使DFT具有了实用价值。

如果对Cooley和Tukey的论文感兴趣的话，下面是原始链接：

Tukey C J W . An Algorithm for the Machine Calculation of Complex Fourier Series[J]. Mathematics of Computation, 1965, 19(90):297-301.

由于的计算是消耗时间大户，所以FFT算法从两个方面入手来加速DFT：

1. 把N点DFT逐次分解几个为长度较短的DFT来计算，降低计算的规模；
2. 利用的周期性和对称性，在DFT运算中进行归类，减少运算次数。