86 Fast Fourier Transform Fast Fourier Transform 快速计算C∑x(0=0,…,NJ,其中甲=24(3) 直接计算需复数乘法N2次降到N·logN 由于W的周期性W哗4=W5,Wk实际上只有w0wN 这N个不同的值。若N为偶数,则W只有N/2个 不同值。 先合并同类项,再做乘法。 Im gonna need some magic here§6 Fast Fourier Transform  Fast Fourier Transform     1 0 N k k j C j xk W         N i W e 2 快速计算 ( j = 0, 1, …, N1)，其中 直接计算需复数乘法 N 2 次  降到 N · logN 由于W 的周期性W qN+s = W s , W k j实际上只有 这 个不同的值。若 N 为偶数，则W k j只有 个 不同值。 0 1 ... N  W W N N / 2 先合并同类项，再做乘法。 I’m gonna need some magic here …