快速傅里叶变换(Fast Fourier Transform) FFT:分治 输入：n次多项式p(x)=∑oax 输出：p(x)在n+1次单位根上的值 计算(n+1)/2次多项式在 计算(m+1)/2次多项式在 (n+1)/2次单位根上的值 (n+1)/2次单位根上的值 只需要o(n)次操作合并 23 快速傅里叶变换 (Fast Fourier Transform) 23 输入：�次多项式� � = ∑"*$ ( �"�" 输出：� � 在n+1次单位根上的值 计算(� + 1)/2次多项式在 (� + 1)/2 次单位根上的值 计算(� + 1)/2次多项式在 (� + 1)/2 次单位根上的值 FFT：分治 只需要O(n)次操作合并