容易推导出,对N=2,执行一个以2为底的完整的FFT,只需 要进行2=2Ng2N次复数乘法和AN=Ng2N次复数加法。由于 log, N 0,N N 因此它比原来需要№次运算的直接算法在数量级上有了重大改进, 节省的工作量相当惊人,比如,对N=20=1024,原算法的复数乘法 次数就超过FFT的200倍!容易推导出，对N k = 2 ，执行一个以 2 为底的完整的 FFT，只需 要进行 kN N N 2 12 = 2 log 次复数乘法和kN N N = log2 次复数加法。由于 log2 0 N N → ， N → ∞， 因此它比原来需要 N 2 次运算的直接算法在数量级上有了重大改进， 节省的工作量相当惊人，比如，对 N = 2 1024 = 10 ，原算法的复数乘法 次数就超过 FFT 的 200 倍！