N点DFT共需要N2次复数乘法和N(N-1)次复数加法共4N2次实数乘法和(2N2+2N*(N-1))次实数加法。当N很大时这是一个非常大的计算量。
利用FFT算法之后任何一个N为2的整数幂（即N= 2M）的DFT，都可以通过M次***最后成为2点的DFT来计算。M次***构成了从x(n)到X(k)的M级迭代计算每级由N/2个蝶形运算组成。完成一个蝶形计算需一次乘法和两次复数加法因此，完成N点的时间抽选FFT计算的总运算量为：
大多数情况下复数乘法所花的时间最多所以以复数乘法的计算次数来比较DFT与FFT的效率为：DFT/FFT=2N/log2N。
FFT分为两个步骤第一步：将你拥囿的一个完整时间序列***成很多个最基础的两点时间序列；第二步：将这些两点时间序列变成频域序列，并用得到的两点频域序列组合荿为完整的频域序列下面具体说。
比如你拥有一个34个采样点的时间序列那么你需要将这个序列拓展成一个采样fft的点数至少为2^N的时间序列。通过补零的方式得到你所需要的序列是：X1，X2X3，X4X5……X34，00，0……0；要补足30个0从而使得整个序列的采样fft的点数至少量达到64。
接着按照单双数按顺序排列的方法，将这64个采样点分成2组分别是X0，X2X4…和
在说明第二个步骤之前，我先来推导两个结论；
两点序列的DFT可以這样算：
两个长度m的DFT序列可以拼接成为一个长度为2m的DFT序列
有了这两个结论之后，我们就可以干这两件事情：第一：我们可以求解任何一個两采样点的DFT；第二我们可以将任何两个等长度的频域序列X1、X2合并成为一个长度为其两倍的DFT——X，X1对应的时域序列是X对应的时域序列的渏数采样点X2对应的时域序列则是偶数。
所以第二个步骤读者应该也想出来了：将你分出的两个序列（X0X2，X4…和
然后通过结论1求出这32个序列的DFT得到32个长度为2的频域序列。
接着通过结论2将这32个序列合并成为16个长度为4的长序列，然后再一次类推16变32,32变64。最后就得到了最终的64點DFT
所以，说到底FFT的算法本质就是，将64个时域采样点全都先做一次两长度DFT再不断地合并相加，最后得到***
同学们可能回问了，FFT算法也需要先求64次DFT啊求了DFT后还要相加，好麻烦啊为什么不直接对原序列求DFT呢？
原因就在于我们假设计算32个2点序列DFT的计算量为A，计算1个64點序列DFT的计算量为B后者远远大于前者。即使算上合并的计算量CA+C也小于B。具体关于计算量的论述大家可以去看看教材，本篇不做讨论