fft算法为什么算的快？

fft算法为什么算的快？

主要是FFT很巧妙的调整了计算的顺序,使得中间的一些计算结果可以重复使用,通过这样的方式就可以降低整个算法的计算量了. 至于具体是怎么实现这一点的,你可以去找一本信号处理有关的书来看看.其实原理还是很简单的.

离散Fourier变换按照最平凡的方式来算需要Θ(N^2)的运算量, 但FFT可以把复杂度降到Θ(N*logN), 并且NlogN之前的系数也挺小, 所以就要快很多