[学习笔记]FFT——快速傅里叶变换

大力推荐博客：

傅里叶变换(FFT)学习笔记

一、多项式乘法：

我们要明白的是：

FFT利用分治，处理多项式乘法，达到O(nlogn)的复杂度。（虽然常数大）

FFT=DFT+IDFT

DFT:

本质是把多项式的系数表达转化为点值表达。因为点值表达，y可以直接相乘。点值表达下相乘的复杂度是O(n)的。

我们分别对两个多项式求x为$\omega_n^i$时的y值。

然后可以O(n)求出乘积多项式x为$\omega_n^i$时的y值。

求法：

把F(x)奇偶分类。

$FL(x)=a_0+a_2x+...+a_{n-2}x^{n/2-1}$

$FR(x)=a_1+a_3x+...+a_{n-1}x^{n/2-1}$

$F(x)=FL(x^2)+xFR(x^2)$


带入那些神奇的单位根之后，
发现有：

$0<=k<n/2$

$F(\omega_n^k)=Fl(\omega_{n/2}^k)+\omega_{n}^kFR(\omega_{n/2}^k)$


$F(\omega_n^{k+n/2})=Fl(\omega_{n/2}^k)-\omega_{n}^kFR(\omega_{n/2}^k)$

我们只要知道Fl、FR多项式在那n/2个位置的点值，那么就可以知道F那n个位置的点值了。

分治就可以处理出来。



IDFT：

经过一系列矩阵的运算之后，，，，

可以得到：

$b_k=[(ω_n^{-k})^0y_0+(ω_n^{-k})^1y_1+(ω_n^{-k})^2y_2+...+(ω_n^k)^{n-1}y_{n-1}]/n$

可以把y当做系数，

只要知道，当x是一系列w的时候，值是多少。

那么就求出来了$b_k$

FFT再写一遍。

注意这里带入的是$ω_n^{-k}$

开始的$tmp$有所不同

[学习笔记]FFT——快速傅里叶变换

原文：https://www.cnblogs.com/Miracevin/p/9994262.html