多项式乘法
A(x)=a0+a1∗x+a2∗x2+a3∗x3+...+an∗xn
B(x)=b0+b1∗x+b2∗x2+b3∗x3+...+bn∗xn
C(x)=A(x)∗B(x)=c0+c1∗x+c2∗x2+c3∗x3+...+c2n∗x2n
暴力解法
两层循环，复杂度是O(n2)
分治算法
A(x)=(a0+a1∗x+a2∗x2+a3∗x3+...+an2−1∗xn2−1)+(an2+...+an)∗xn2+=A1+A2∗xn2
B(x)=(b0+b1∗x+b2∗x2+b3∗x3+...+bn2−1∗xn2−1)+(bn2+...+bn)∗xn2+=B1+B2∗xn2
C(x)=A(x)∗B(x)=A1∗B1+A2∗B1∗xn2+A1∗B2∗xn2+A2∗B2∗xn
A1∗B1,A2∗B1,A1∗B2,A2∗B2都是规模为n2的多项式乘法
T(n)=4T(n2)+c∗n=O(n2),可是还是没提升，我们可不可以做更少次的乘法呢
C(x)=A(x)∗B(x)=A1∗B1+A2∗B1∗xn2+A1∗B2∗xn2+A2∗B2∗xn
=((A1+A2)∗(B1+B2)−A1∗B1−A2∗B2)∗xn2+A1∗B1+A2∗B2∗xn
这样我们把它转换为了3次乘法
T(n)=3T(n2)+c∗n=O(nlog23)<O(n2)
快速傅里叶变换
我们发现A(x)B(x)多项式相乘，可以看成N个离散数据(a0,a1,…an)和N个离散数据(b0,b1,…bn)的卷积操作，即信号处理里的时域卷积，而域卷积对应的是频域相乘，所以我们把多项式相乘的步骤转换为
1. 把A(x) B(x)系数对应的离散信号数据进行快速傅里叶变换到频域 ，O(nlogn)
2. 频域对应分量相乘，O(n)
3. 傅里叶逆变换，O(nlogn)
所以整体的复杂度就是O(nlogn)
分治法求快速傅里叶变换
解释:
傅里叶级数Aj即是离散数据(a0,a1,a2...aN−1)在各个频段e−2πijk/N的分量, 它的求法可以转化为求多项式a(x)=∑N−1k=0akxk在wj的取值，即Aj=a(wj), 我们需要求A0−>AN−1或a(w0)−>a(wN−1),N=2n
a(x)=a0+a1∗x+a2∗x2+a3∗x3+...+aN−1∗xN−1
b(x)=a1+a3∗x+a5∗x2+a7∗x4+...+aN−1∗xN−22
c(x)=a0+a2∗x+a4∗x2+a6∗x4+...+aN−2∗xN−22
注意这里的a和离散数据(a0,a1,a2...aN−1)里的a不是一个意思，这里的a只是个函数名称，可改成f或者其他
而a(x)可以拆分为奇偶两项,a(x)=b(x2)∗x+c(x2)
而且a(wj)的前一半和后一半都可以用奇偶项b(x^2)和 c(x^2)得到，所以可以利用分治
T(N)=2T(N/2)+cN,T(n)=O(NlogN)
参考:
多项式乘法与快速傅里叶变换
两个n项多项式相乘采用分治算法的时间复杂度怎样计算？
【算法笔记】多项式快速算法——快速傅里叶变换
FFT算法学习笔记
