快速傅里叶变换

简述

$F(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0$

$G(x)=b_nx^n+b_{n-1}x^{n-1}+...+b_0$

求$C(x)=F(x)G(x)$

暴力求解复杂度$O(n^2)$

因为$n+1$个$x$不同的点可以唯一确定一个次数不超过$n$的多项式，因而我们可以从$F(x)$中选取一些点$(x_0,F(x_0))...(x_k,F(x_k))$，在$G(x)$中选取一些点$(x_0,G(x_0))...(x_k,G(x_k))$

那么显然点$(x_i,F(x_i)G(x_i))$在$y=C(x)$上，可以用这些点得到$C(x)$的表达式

因此FFT算法流程可以表示为：

系数表达式转为点值表达(DFT) -> 点值表达相乘 -> 点值表达转为系数表达(IDFT)

复数的一些性质

1. 复数相乘：模长相乘，辐角相加

2. 对于$w^n=1$的解（称为单位根，$w_n^k$为第$k$个单位根）有以下性质

   1. $w_n^0=1$
   2. $w_n^k=(w_n^1)^k$
   3. $w_n^j*w_n^k=w_n^{j+k}$
   4. $w_{2n}^{2k}=w_n^k$
   5. 若$n$为偶数，$w_n^{k+n/2}=-w_n^k$

   记不住没关系，看不懂的时候回来找公式就好

参考资料

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

浅谈FFT (opens new window)

浅谈FFT--从DFT到CZT,及一些技巧 (opens new window)