要煦长水 之V Z寸 新水 实本 之2 §1 FFT 算法的基本思想 ∑ − = = 1 0 ) ( ) ( : N n kn N W n x k X DFT 1 0 − ≤ ≤ N k Nj N e W π2 − = 1、直接计算DFT存在的问题： 设 x(n) 为复数 对每个k，计算 X(k)，共需N次复乘及N-1次复加。 N个k，则共需 N2 次复乘及N(N-1)次复加。 4N2 次实乘及 2N(2N-1)次实加