FFT（Fast Fourier Transformation）是离散傅氏变换（DFT）的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。
以上内容摘自百度百科,其实看了等于没看
首先先要知道一些预备知识：
1、多（door♂）项式
2、复数的运算（不是负数）
3、下面开始讲吧……
首先，多（door♂）项式是蛤？
也可表示为
这个就是多项式，一般是吧高次项写在前面，我这里这样写只是为了方便。
那么FFT是用来干蛤的？
这个问题问得好，FFT是用来算两个多项式相乘的。
那不可以暴力乘吗（）？
那暴力可以做到 吗？
。。。。
---------------------------------------------------------------------------------先分个鸽-------------------------------------------------------------------------------------
首先先要有复数运算的知识
我们知道 （是个虚数）
那么对于形如，其中a,b为实数，i为虚数的东东我们称它为复数
a 为实部，bi为虚部。
加法运算： 实部+实部 虚部+虚部
减法运算：同上，‘+’ —> ‘-’
乘法运算：就和正常的多项式乘法差不多，只不过要注意
除法运算：分数上下同时乘分母的共轭
即：
一个复数共轭就是一个实部相同，虚部为相反数的复数
如的共轭是
一个复数的共轭通常表示为
可得
因为所以分母必定为实数
对于 我们还可以这样子表示
其中a为实轴，b为虚轴， 就可以表示为在这样一个二维平面上的一个点
复数乘法在平面中就是辐角相加，模长相乘 （这个用三角函数可以证明，这里就不多说了）
真香
证明：对于可以表示为其中为辐角,为半径（即模长），然后相乘就直接r相乘指数相加就行了
