【OI向】快速傅里叶变换(Fast Fourier Transform) FFT的作用
在学习一项算法之前,我们总该关心这个算法究竟是为了干什么。
（以下应用只针对OI）
一句话:求多项式乘法(当然它的实际用处很多)
设多项式
\(A(x)=a_0+a_1x+a_2x^2+\ldots+a_nx^n\)
\(B(x)=b_0+b_1x+b_2x^2+\ldots+b_mx^m\)
我们想求 \(F(x)=A(x)B(x)=\sum\limits_{i=0}^n\sum\limits_{j=0}^ma_ib_jx^{i+j}\)
肉眼可见的复杂度\(O(nm)\)
而使用一般的FFT则复杂度能够在\(O(nlogn)\) （实则带比较大的常数,但数据范围大时肯定比\(O(nm)\)好）
写这篇博客是为了让自己和看到的人能够梳理一遍FFT这个算法。
以下FFT的实现使用比较常见的复数单位根做法。
前置知识 首先要知道复数是什么,高中选修即有,网上资料也很多,不赘述,这里只讲FFT直接相关。
1 复数单位根 定义: \(z^n=1\) 那么 \(z\) 就是n次的单位根
对于一个\(n\)次单位根,就是将复数单位圆等分成\(n\)份,每个数 \(w_n^k (k\in[0,n-1) )\) 就被称作n次的第k个单位根
如图
图中表示了所有8次单位根,其中\(w_8^0=1,w_8^1=1+i,w_8^2=i,w_8^3=-1+i\ldots\) 所谓单位根就是这些复数,它们的平方均为1。
虽然单位根的次数\(n\)在定义上可以取全体正整数,但是我们在FFT中只需要考虑n为2的整数次幂,以方便我们利用性质。
单位根有一些性质,我们先列出来看看 （下边的n均为2的整次幂!）
0 单位根乘法 \(w_n^i\times w_n^j=w_n^{i+j}\),这个性质实际上不能叫性质,从复数乘法,辐角的概念出发即能够得证。
1 消去引理 \(w_{2n}^{2k}=w_n^k\)
理解,可以看到 \(2k\) 和 \(k\) 在 \(2n\) 和 \(n\) 中占的比例是相同的,联想单位圆即可(\(w_8^2\)显然等于\(w_4^1\),均为1)
2 折半引理 我看了好几篇博客,包括知乎,对折半引理的说法是: 对于 \(n\) 等于 \(2\) 的整次幂, \(w_n^k\)经过平方可以得到所有\(w_{\frac{n}{2}}^k\)(单纯来说只需要\(n\)是二的倍数就好)
两个小性质都可以证明
\(w_n^{2k}=w_{\frac{n}{2}}^k\)
由消去引理,这个小性质是显然的。从这个性质出发,如果 \(k\) 取遍\([0,n-1]\),那么首先右边是全了,对于左边,\(2k\in[0,2n-2]\),经历了一次循环, (按道理这里需要指出一个循环性质,但我觉得没必要) \(w_n^{k+n}=w_n^{k}\times w_n^{n}\), 而\(w_n^n\)即\(w_n^0=1\),所以 \(2k\) 过了\(n-1\)之后会经过\(\frac{n}{2}\)个相同的点
\(w_n^k=-w_n^{k+\frac{n}{2}}\)
旋转\(180^\circ\) 事情变得显然;从复数乘法的角度来说也可以：\(w_n^{k+\frac{n}{2}}=w_n^k\times w_n^{\frac{n}{2}}\),而\(w_n^{\frac{n}{2}}\)恰好为\(-1\)。
那么这个性质告诉我们前一半\(k\in[0,\frac{n}{2}-1]\)和后一半 \(k\in[\frac{n}{2},n-1]\)的平方是一样的,所以同理,两半的平方值是一样的,也就是两部分平方只确定了\(\frac{n}{2}\)个值,那么利用前边第一个小性质,我们不需要循环性质就能够证明折半引理。
折半引理告诉我们,如果知道了n的所有单位根,那么\(\frac{n}{2}\)的单位根我们可以知道,反之,我们利用第二个性质也可以从\(\frac{n}{2}\)的所有单位根,加一个负号,就能推出所有的 \(n\) 次单位根。
3 求和引理 \(\sum\limits_{i=0}^{n-1}w_n^k=0\)
从折半引理看,我们把 \(w_n^k\) 分成两部分\(w_n^a (a\in[0,\frac{n}{2}-1] ),w_n^b(b\in[\frac{n}{2},n-1])\),也就是圆的上半部分和下半部分,对应有每个\(w_n^a+w_n^b=0\)，实际上是\(w_n^a+w_n^{a+\frac{n}{2}}=0\),所以两部分的累加和就是0(我们上边已经假设n是2的整次幂了,所以一定是相同大小的两部分)
单位根的表示 首先简单说一下辐角,在复数平面上,从实数轴正半轴逆时针旋转到复数\(z\)到原点的连线,中间经过的角度就叫做辐角(大小在\(2\pi\)之内)
从圆的知识类比一下,我们可以知道