FFT（没有参考书）

前置知识
复数

多项式表示
朴素表示法：我们平时的方法 a0 + a1x^1 + a2x^2 + …
点值表示法：给定一个x坐标，带入到多项式中，会得到一个f(x)值。多项式多少维，我们就弄多少个点。最后{（x1,f(x1)） (x2,f(x2)) …..}就是点值表示法。

点值表示法在处理两个多项式相乘的时候速度更快。是O(N)的。这是因为相同的x值可以直接变成->
(x,f(x_1) *f(x_2) )

DFT
个人理解所谓离散傅里叶变换就是朴素表示的多项式到点值表示的多项式的转换过程。
转换的过程就是不断的取x，算fx。
我们希望x是1之类的数，这样不管x怎么次方都是1，算起来方便。
那这样我们怎么选x呢？

我们需要在这个圈上选点。
但这个圈是连续的，不方便。
所以我们通常根据多项式的最高次项进行切分。比如最高次项是7（8-1），我们就分成8份。

这样我们就有八个点了

单位根是什么

单位根的性质

这三个性质类似于 加一个周期值不变，奇变偶不变和w80 == w88

FFT

FFT算法

IFFT