快速傅里叶变换FFT简明教程

给出长度为 n n n的多项式 f ( x ) = ∑ i = 0 n ? 1 a i x i f(x)=\sum_{i=0}^{n-1}a_{i}x^{i} f(x)=∑i=0n?1aixi和长度为 m m m多项式 g ( x ) = ∑ i = 0 m ? 1 b i x i g(x)=\sum_{i=0}^{m-1}b_{i}x^{i} g(x)=∑i=0m−1​bi​xi。求解多项式 h ( x ) = f ( x ) × g ( x ) h(x)=f(x)\times g(x) h(x)=f(x)×g(x)。 ( 1 ≤ n ≤ 1 0 5 ) (1\leq n\leq 10^{5}) (1≤n≤105)

多项式的两种表示方法，系数表示法和点值表示法。 系数表示法：我们存储 f ( x ) f(x) f(x)的每一项 x i x^{i} xi的系数 a i a_{i} ai​。 点值表示法：由大家都知道知， N N N个点可以确定一个最高次为 N − 1 N-1 N−1多项式，所以我们可以存储多项式上任意 N N N个点，来确定这个多项式。

点值表示法有个性质是，对于多项式 f f f的一个点值 ( x , y 1 ) (x,y_{1}) (x,y1​)，和多项式 g g g的一个点值 ( x , y 2 ) (x,y_{2}) (x,y2​)，可以得到两个多项式相乘的多项式 h h h在横坐标为 x x x处的点为 ( x , y 1 × y 2 ) (x,y_{1}\times y_{2}) (x,y1​×y2​)。

所以在对于长度为 n n n的多项式 f f f和长度为 m m m的多项式 g g g做乘法时，我们可以算出 f f f的 n + m − 1 n+m-1 n+m−1个点值和 g g g的 n + m − 1 n+m-1 n+m−1个点值，且要求两个多项式点值所取的 x x x相同。 我们就可以通过遍历算出这 n + m − 1 n+m-1 n+m−1个横坐标的点值纵坐标相乘，来得到相乘后多项式的 n + m − 1 n+m-1 n+m−1个点值，也就是新多项式的点值表示法。 (注意：虽然我们存储 f f f只需要 n n n个点值，但是为了计算出长度为 n + m − 1 n+m-1 n+m−1的 h h h，我们仍要先得到 f f f的(n+m-1)个点值)

因此，假如我们可以通过 o ( n l o g n ) o(nlogn) o(nlogn)的办法，将系数表示法转化为点值表示法，然后将两个多项式点值 o ( n ) o(n) o(n)相乘，最后通过 o ( n l o g n ) o(nlogn) o(nlogn)的办法将点值表示法转化回系数表示法，就可以解决这个问题了。

后面来介绍如何将系数表示发和点值表示法进行转换。

对于没有周期的函数，我们可以认为其周期为 ∞ \infty ∞，用无穷个周期函数去拟合。 同理，对于一个长度为 N N N的离散多项式 x ( n ) ( n = 0 , 1 , 2.. N − 1 ) x(n) (n=0,1,2..N-1) x(n)(n=0,1,2..N−1)，可以通过 N N N个周期函数来拟合。（ N N N个周期函数只能拟合 N N N个点，不能用来拟合连续多项式函数） 由此我们得到离散傅里叶级数展开式如下。 X ( k ) = ∑ n = 0 N − 1 x ( n ) e − 2 π i k n N X(k)=\sum_{n=0}^{N-1}x(n)e^{-2\pi ik\frac{n}{N}} X(k)=n=0∑N−1​x(n)e−2πikNn​ 其中 e − 2 π i k n N = c o s ( − 2 π k n N ) + i s i n ( − 2 π k n N ) e^{-2\pi ik\frac{n}{N}}=cos(-2\pi k\frac{n}{N})+isin(-2\pi k\frac{n}{N}) e−2πikNn​=cos(−2πkNn​)+isin(−2πkNn​)是关于 n n n的周期为 N N N的函数。（由欧拉公式 e i x = c o s x + i s i n x e^{ix}=cos x+isin x eix=cosx+isinx得）

对于变换后得到的 X ( n ) X(n) X(n)，我们可以通过离散傅里叶逆变换公式得到原函数 x ( n ) x(n) x(n)。与 D F T DFT DFT公式差不多，在原来的基础上 i i i变成了 − i -i −i，前面乘上一个 1 N \frac{1}{N} N1​。公式如下。 x ( n ) = 1 N ∑ k = 0 N − 1 X ( k ) e 2 π i k n N x(n)=\frac{1}{N}\sum_{k=0}^{N-1}X(k)e^{2\pi ik\frac{n}{N}} x(n)=N1​k=0∑N−1​X(k)e2πikNn​

由前面讲过的，我们要解决的核心问题就是，算出多项式的 N N N个点值。 大致做法是，我们求出函数在离散傅里叶变换后的N个点值，由点值乘出新多项式后，再将其逆变换回系数表示法。

我们先来观察式子 D F T DFT DFT的式子。 我们为了简化式子，我们把 e 2 π i k N e^{\frac{2\pi ik}{N}} eN2πik​用 W N W_{N} WN​代替。( W N W_{N} WN​是一个关于 k k k的函数) 得到式子如下。 X ( k ) = ∑ n = 0 N − 1 x ( n ) W N n ( k ) X(k)=\sum_{n=0}^{N-1}x(n)W_{N}^{n}(k) X(k)=n=0∑N−1​x(n)WNn​(k) 然后观察 W N W_{N} WN​如下。 W N ( k ) = e 2 π i N = c o s ( 2 π k N ) + i s i n ( 2 π k N ) W_{N}(k)=e^{\frac{2\pi i}{N}}=cos(\frac{2\pi k}{N})+isin(\frac{2\pi k}{N}) WN​(k)=eN2πi​=cos(N