学习FFT（快速傅里叶变化）小记

（话说这是1年前的坑啊）

楔子

话说最近被什么“初三不会SAM就退役”等鬼话给迷惑了。
左学右学了好久。
还是不会SAM啊
symbol说不可以信这些鬼话。
然后又有这么一句话“初三不会FFT就退役”
就被诱惑去学FFT了。

正文

注：这些内容是在多项式专题讲师的指导下学的，不全也别怪我，

复数

引用一下定义

我们把形如a+bi（a,b均为实数）的数称为复数.
其中a称为实部，b称为虚部，i称为虚数单位.
当虚部等于0时，这个复数是实数。
实部等于0时，常称z为纯虚数。
i=√-1

有了复数的定义之后，我们再看看另外的东西——
复平面

复平面是一个坐标系
横轴表示实数，纵轴表示虚数
复平面上的点都能表示所有的复数
点(x,y)表示复数x+iy
一个复数z=a+bi在复平面上到原点的距离为a2+b2sqrt{a^2+b^2},称此为复数z的模长r，记作∣z∣|z|

这里有一个神奇的图可以帮助理解：
这里写图片描述
你问我什么可以画这么个坐标轴？
因为i为虚数，所以可以在x坐标上表示，也就是把每个单位长换做是i就差不多了。
打死也不说是数学老师上函数课无聊时讲的
然后我们来找找其中的一些神奇的性质。
这里写图片描述
首先，当Z不在原点的时候，即Z<>0 （讲师PPT上是Z!=0吓得我以为是阶乘）OZ→overrightarrow {OZ}与x轴的夹角记作是Arg Z
那么Z就可以表示为
Z=∣z∣∗(cos(ArgZ)+i∗sin(ArgZ))Z=|z|*(cos(Arg Z)+i*sin(Arg Z))
什么意思呢？
这里写图片描述
首先，看看sin与cos
sin表示a/c
cos表示b/c
然后上面的式子就为：
Z=∣z∣∗(a/∣z∣+i∗b/∣z∣)Z=|z|*(a/|z|+i*b/|z|)
Z=a+i∗bZ=a+i*b
符合原来的定义。
然后这个就叫做是三角表示。

然后我们有这个东东了之后，是否可以大胆地想：“把两个复数的乘积用三角表示表示出来？”
Z1=r1∗(cos(φ)+i∗sin(φ))//φ=ArgZ1,r1=∣z1∣Z1=r1*(cos(varphi)+i*sin(varphi))// varphi=Arg Z1,r1=|z1|
Z2=r2∗(cos(θ)+i∗sin(θ))//θ=ArgZ2,r2=∣z2∣Z2=r2*(cos( heta)+i*sin( heta))// heta=Arg Z2,r2=|z2|
合并起来：
Z1Z2=r1∗r2∗((cos(φ)cos(θ)−sin(φ)sin(θ))+i∗(cos(φ)sin(θ)+cos(θ)sin(φ)))Z1Z2=r1*r2*((cos(varphi)cos( heta)-sin(varphi)sin( heta))+i*(cos(varphi)sin( heta)+cos( heta)sin(varphi)))
∵三角恒等式，也就是下面的东东ecause三角恒等式，也就是下面的东东
这里写图片描述
证明？必修四上似乎有讲，当然，和百度百科是一样的。
（自百度百科）
取直角坐标系，作单位圆；取一点A，连接OA，与X轴的夹角为α，取一点B，连接OB，与X轴的夹角为β， 则OA与OB的夹角即为α-β
∵A(cos(α),sin(α)),B(cos(β),sin(β))∵A(cos(α),sin(α)),B (cos(β),sin(β))
∴OA→=(cos(α),sin(α)),OB→=(cos(β),sin(β))∴overrightarrow{OA}=(cos(α),sin(α)),overrightarrow{OB}=(cos(β),sin(β))
∴OA→⋅OB→=∣OA→∣∣OB→∣cos(α−β)=cos(α)cos(β)+sin(α)sin(β)∴overrightarrow{OA}·overrightarrow{OB}=|overrightarrow{OA}| |overrightarrow{OB}|cos(α-β)=cos(α)cos(β)+sin(α)sin(β)
∵∣OA→∣=∣OB→∣=1∵|overrightarrow{OA}| = |overrightarrow{OB}| = 1
∴cos(α−β)=cos(α)cos(β)+sin(α)sin(β)∴cos(α-β)=cos(α)cos(β)+sin(α)sin(β)
取β=−ββ=-β，可得cos(α+β)=cos(α)cos(β)−sin(α)sin(β)cos(α+β)=cos(α)cos(β)-sin(α)sin(β)
下面那条式子是同理。

然后根据上面的三角恒等式，可以发现——
Z1Z2=r1∗r2∗(cos(φ+θ)+i∗sin(φ+θ))Z1Z2=r1*r2*(cos(varphi+ heta)+i*sin(varphi+ heta))
这样好！
那么总结一下就是——
我们得到了两个复数相乘的运算法则：模长相乘，幅角相加。

然后我们继续看看其他神奇的东西：
考虑一个方程：
xn=1x^n=1
求x的复数解。
直接告诉你结论——
有n个解，第i个解为:xi=cos(2πin)+i∗sin(2πin)有n个解，第i个解为:xi=cos(frac{2pi i}{n})+i*sin(frac{2pi i}{n})
证明？
由于模长为1，然后可以画一个圆，每次就把圆的一条边旋转那么n次，然后回到0。
很好理解对吧？

好的，复数的一些内容大致到此结束。
这么快？因为这些都是为后文做铺垫滴~~~

FFT

其实就是这么个问题——
给出两个多项式A(x)，B(x)
要求快速求出C(x)=A(x)*B(x)

一些定义：
1、次数界：最高次数+1即为次数界。
然后对于一个次数界为n的多项式A(x)可以表示为：A(x)=∑i=0n−1ai∗xiA(x)=sum_{i=0}^{n-1} a_i*x^i
aia_i表示每一项的系数。
2、点值与点值表达：
一个次数界为n的多项式A(x)=∑i=0n−1ai∗xiA{(x)}=sum_{i=0}^{n-1}a_i*x^i的点值表达就是一个由n个点值对所组成的集合：{(x0,y0),(x1,y1),...,(xn−1,yn−1){(x_0,y_0),(x_1,y_1),...,(x_{n-1},y_{n-1})}}
yk=A(xk)y_k=A(x_k)
举个例子：
比如A(x)=x2+3x+5A(x)=x^2+3x+5
那么任意一个点值表达为：(−1,3)(0,5)(1,10)(-1,3)(0,5)(1,10)
第一个的意义是当x=-1时，A(x)=3
3、差值表达：
插值运算是根据多项式的点值表示确定多项式系数表示中的系数，是点值运算的逆运算
意思就是把一个点值表达式变成差值表达。

注意：任意一个点值表达只能表示一种多项式，这叫做：多项式插值的唯一性
这是个定理，至于证明的话，我不会~

那么我们就可以知道FFT的工作原理——
注意：提示：对于次数界为n的多项式A与次数界为m的多项式B，AB的多项式C的次数界为n+m-1*
第1步:点值运算 构造长度为n+m-1的点值,求得A与B的点值表示
A表示为：{(x0,y0),(x1,y1),...,(xn+m−2,yn+m−2){(x_0,y_0),(x_1,y_1),...,(x_{n+m-2},y_{n+m-2})}}
B表示为：{(x0,y0′),(x1,y1′),...,(xn+m−2,yn+m−2′){(x_0,y&#x27;_0),(x_1,y&#x27;_1),...,(x_{n+m-2},y&#x27;_{n+m-2})}}
第2步:逐点相乘 那我们可以得知C的点值表示
C表示为：{(x0,y0∗y0′),(x1,y1∗y1′),...,(xn+m−2,yn+m−2∗yn+m−2′){(x_0,y_0*y&#x27;_0),(x_1,y_1*y&#x27;_1),...,(x_{n+m-2},y_{n+m-2}*y&#x27;_{n+m-2})}}
第3步:插值运算 通过C的点值表示求出多项式C的每项系数

具体流程：
第1步：根据霍纳法则可得：A(x)=a0+x0(a1+x0(a2+x0(...(an−2+x0∗an−1)...)))A(x)=a_0+x_0(a_1+x_0(a_2+x_0(...(a_{n-2}+x_0*a_{n-1})...)))
不会的点这里
https://baike.baidu.com/item/霍纳法则/4822190?fr=aladdin
第2步：使用lu分解。时间复杂度为O(n3)O(n^3)
不会的点这里
https://baike.baidu.com/item/lu分解/764245?fr=aladdin
第2.5步：使用拉格朗日。时间复杂度O(n2)O(n^2)
不会的点这里
https://baike.baidu.com/item/拉格朗日公式#3
当然，上述的都不重要，重点在后。

N次单位根的性质——
我们称为ωnomega_n=ωn1omega_n^1主n次的单位根
别看它那么深奥，则其实就是之前方程中的x。
我们可以发现，n的单位根的模长都为1，且两两相临的单位根的夹角都相等。
那么：ωni=ωn∗ωni−1omega_n^i=omega_n*omega_n^{i-1}
所以说这是一个等比数列。公比p=主n次的单位根
这里写图片描述
这张图是复平面上 主8次的单位根 的图。
我们找找一些性质——
1、ωnn=ωn0=1omega_n^n=omega_n^0=1
2、ωnxωny=ωnx+y=ωn(x+y)modnomega_n^xomega_n^y=omega_n^{x+y}=omega_n^{(x+y)mod n}
因为两个相乘就相当于两个相加（显然），然后就相当于旋转了(x+y)次。如果mod一下，那么就相当于转了很多圈回到了原来的一个值。
3、ωnx=ωnn+xomega_n^x=omega_n^{n+x}
证明与上面的一样。
4、群的性质：满足ωnx&lt;&gt;ωnyomega_n^x&lt;&gt;omega_n^y当且仅当x mod n<>y mod n
5、消去引理：ωdndx=ωnxomega_{dn}^{dx}=omega_n^x
6、折半引理：(ωni)2=(ωni+n2)2=ωn2i(当2∣n时)({omega_n^i})^2=(omega_n^{i+ frac n2 })^2=omega_n^{2i} (当2|n时)
证明：
∵(ωni)2=ωn2iecause({omega_n^i})^2=omega_n^{2i}
∵ωn2i=ωn2i+n=(ωni+n2)2ecauseomega_n^{2i}=omega_n^{2i+n}=(omega_n^{i+ frac n2 })^2
∴(ωni)2=(ωni+n2)2 herefore({omega_n^i})^2=(omega_n^{i+ frac n2 })^2
事实上：ωni=−ωni+n2omega_n^i=-omega_n^{i+ frac n2 }
很好理解恩？
7、求和引理： 对于任意正整数n和非负整数k，且n不是k的倍数时，满足：∑i=0n−1(ωnk)i=0sum_{i=0}^{n-1}(omega^k_n)^i=0
证明：
运用等比数列：
∑i=0n−1(ωnk)i=1−(ωnk)n1−ωnk=1−(ωnn)k1−ωnk=1−1k1−ωnk=0sum_{i=0}^{n-1}(omega^k_n)^i=frac{1-(omega_n^k)^n}{1-omega_n^k}=frac{1-(omega_n^n)^k}{1-omega_n^k}=frac{1-1^k}{1-omega_n^k}=0
8、不知道什么引理或定理：
ωnk+n2=−ωnkomega_n^{k+frac n2}=-omega_n^k
至于为什么，就是根据它在图像上的向量求的。

然后就是fft的关键：

考虑多项式
A(x)=∑i=0n−1ai∗xi=a0∗x0+a1∗x1+a2∗x2+……+an−1∗xn−1A(x)=sum_{i=0}^{n-1}a_i*x^i=a_0*x^0+a_1*x^1+a_2*x^2+……+a_{n-1}*x^{n-1}
我们把这个玩意按照下标奇偶性来分个类。
=(a0∗x0+a2∗x2+……+an−2∗xn−2)+(a1∗x1+a3∗x3+……+an−1∗xn−1)=(a_0*x^0+a_2*x^2+……+a_{n-2}*x^{n-2})+(a_1*x^1+a_3*x^3+……+a_{n-1}*x^{n-1})
=(a0∗x0+a2∗x2+……+an−2∗xn−2)+x∗(a1∗x0+a3∗x2+……+an−1∗xn−2)=(a_0*x^0+a_2*x^2+……+a_{n-2}*x^{n-2})+x*(a_1*x^0+a_3*x^2+……+a_{n-1}*x^{n-2})
设
A1(x)=a0∗x0+a2∗x+a4∗x2+……+an−2∗xn−22A1(x)=a_0*x^0+a_2*x+a_4*x^2+……+a_{n-2}*x^frac{n-2}2
A2(x)=a1∗x0+a3∗x+a5∗x2……+an−1∗xn−22A2(x)=a_1*x^0+a_3*x+a_5*x^2……+a_{n-1}*x^frac{n-2}2
则
A(x)=A1(x2)+x∗A2(x2)A(x)=A1(x^2)+x*A2(x^2)
设k&lt;=n2k&lt;=frac n 2，然后把ωnkomega_n^k代入xx得到：
A(ωnk)=A1((ωnk)2)+ωnk∗A2((ωnk)2)A(omega_n^k)=A1((omega_n^k)^2)+omega_n^k*A2((omega_n^k)^2)
根据折半引理：
A(ωnk)=A1(ωn2k)+ωnk∗A2(ωn2k)A(omega_n^k)=A1(omega_n^{2k})+omega_n^k*A2(omega_n^{2k})
根据消去引理：
A(ωnk)=A1(ωn2k)+ωnk∗A2(ωn2k)A(omega_n^k)=A1(omega_frac n2^k)+omega_n^k*A2(omega_frac n2^k)
然后再把ωnk+n2omega_n^{k+frac n 2}代入得到
A(ωnk+n2)=A1((ωnk+n2)2)+ωnk+n2∗A2((ωnk+n2)2)A(omega_n^{k+frac n 2})=A1((omega_n^{k+frac n 2})^2)+omega_n^{k+frac n 2}*A2((omega_n^{k+frac n 2})^2)
A(ωnk+n2)=A1(ωn2k+n)−ωnk∗A2(ωn2k+n)A(omega_n^{k+frac n 2})=A1(omega_n^{2k+n})-omega_n^k*A2(omega_n^{2k+n})
A(ωnk+n2)=A1(ωn2k)−ωnk∗A2(ωn2k)A(omega_n^{k+frac n 2})=A1(omega_n^{2k})-omega_n^k*A2(omega_n^{2k})
A(ωnk+n2)=A1(ωn2k)−ωnk∗A2(ωn2k)A(omega_n^{k+frac n 2})=A1(omega_frac n2^k)-omega_n^k*A2(omega_frac n2^k)
继而发现，上面两坨玩意儿只有一个符号变了。
意味着，求出A1(ωn2k)A1(omega_frac n2^k)和A2(ωn2k)A2(omega_frac n2^k)的答案，即可求出A(ωnk)A(omega_n^k)与A(ωnk+n2)A(omega_n^{k+frac n 2})

那么递归！
每一次回溯时只扫当前前面一半的序列，即可得出后面一半序列的答案
得到一个高效算法O(nO(n loglog n)n)

待更

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/RainbowCrown/p/11148347.html