多项式的表示，比如A(x)=3x2+2x+1
- 系数表示法
- 由系数组成的向量 a=(3,2,0)
即 a=(a0,a1,…,an-1) - 点值表示法
- { (0,1) , (1,6) , (2,17) }
即 { (x0,y0) , (x1,y1) , … , (xn-1,yn-1) } 其中yk=A(xk)
如何使用系数表示来求点值表示，称为求值
如何使用点值表示来求系数表示，称为插值
还有两者共有一种求法，
如果 x0 ~ xn-1 互不相同，则M是可逆的，也就是说求值过程我们可以是乘以M，那么插值过程就是通过乘以M-1,范德蒙德求逆矩阵是比其他的要快
多项式乘法
A(x) * B(x) 假如系数表示，使用
于是多项式乘法出现了两条路径
这不是时间变长了，过程变复杂了吗？
看似不通的路只要改进就可以更好，改进如下
- 求值：注意的是我们需要加倍次数界，通过假如n个系数为0的高阶系数，然后使用FFT（快速傅里叶变换）求点值
- 逐点相乘：C(x)=A(x)B(x)
- 插值：计算逆DFT
好了上面讲完了入门，重头戏来了
FFT
在求值的过程我们把式子稍微变一下
一个多项式，可以化成如下形式
这时候我们避免重复计算，我们取值就取几对相反数吧，比如是n个，我们取
±x0,±x1,…,±xn/2-1
大家注意到了吗？很巧妙 !!! 这里把n个点化成了n/2个点在Aeven(x)和Aodd(x)的计算过程(因为取点正负),且次数也减少了一半(观察Aeven(x)和Aodd(x)不难看出)
这时候自然而然的就想到了我们的分治，再递归求解下面的Aeven(x)和Aodd(x)，难道FFT算法就这样了吗？当然还差一点距离，大家仔细观察一下下面
在第一次递归中，我们我取值，是n对相反数，可是到了下面递归，平方和平方怎么可能是相反数！！！我们该怎么办？车到山前必有路，大家能想到复数吗？对没有错，我们这次就要使用复数
是不是很神奇，这次我们找到了7次的8个取值，那假如换成15次的呢，我们又应该怎么找呢？头疼，这里是有规律的！
其实上面的8个取值，是z8的8个复数根
那么16个就是zn的n个复数根，怎么样想到了吗，哈哈没有错 ，取n个就是zn的n个复数根【这里我就不在讲述n次单位复数根】
终于我们可以n次单位复数根借助复数使用分治算法，来求得点值表示了，这也就是快速傅里叶变换，摘自《算法概论》的伪代码
好了，让我们来总结一下，到底什么是快速傅里叶变换(FFT)以及大家所说的离散傅里叶变换(DFT)
下面是《算法导论》对于DFT的描述
也就是说在n个n次单位复数根处求值过程就是DFT
依照上面的算法所需时间θ(n2)，然而我们使用FFT，利用复数单位根的性质，可以在θ(nlgn)时间内计算出DFTn(a)，这里我们使用的是分治法递归思路，DFT的实际应用比如信号处理中需要尽可能快的速度，下面介绍一种更加高效的FFT实现，也就是迭代实现，再把《算法导论》的贴上去，大家可以对比一下
< 值 > = FFT (< 系数 > , point )
插值
很巧的是
< 系数 > = (1/n) FFT (< 值 > , point-1 )
这里还是要说明原因的，再把上面的范德蒙德拿下来看