考虑DFT的运算公式为：
![X(k) = \text{DFT}[x(n)] = \sum_{n=0}^{N-1}{x(n)W_N^{nk}} \quad k=0,1, ..., N-1](https://math.jianshu.com/math?formula=X(k)%20%3D%20%5Ctext%7BDFT%7D%5Bx(n)%5D%20%3D%20%5Csum_%7Bn%3D0%7D%5E%7BN-1%7D%7Bx(n)W_N%5E%7Bnk%7D%7D%20%5Cquad%20k%3D0%2C1%2C%20...%2C%20N-1)
根据上式，可得)
的展开式为：
%20%3D%20x(0)W_N%5E%7B0%7D%20%2B%20x(1)W_N%5E%7Bk%7D%20%2B%20x(2)W_N%5E%7B2k%7D%20%2B%20...%20%2B%20x(N-1)W_N%5E%7B(N-1)k%7D)
其中
。
如果根据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：
- 把N点DFT逐次分解几个为长度较短的DFT来计算，降低计算的规模；
- 利用的周期性和对称性，在DFT运算中进行归类，减少运算次数。
