1.多项式相乘
怎么来表示两个多项式相乘呢？
（1） 在线性代数里面我们是可以用多项式的系数来表示一个多项式，两个多项式的相乘也就是两个多项式的系数分别乘上彼此的系数（交叉相乘求和），最终得到的就是两个多项式相乘的系数所表示的多项式，这样可以确定唯一的多项式。
（2）还有一种表示方法就是用点来确定，叫做值表示法，比如我们所知的两个点确定一条一阶直线，三个点可确定一条二阶曲线，那么推广开来：d+1个点就可以确定d阶的曲线，这样也是唯一确定的。
所以在计算两个多项式相乘结果的时候我们可以采用（1）中的系数相乘法，这样结果的计算复杂度为o（
）,而采用（2）用n+1个点来确定的话那么只需要在两个多项式里面分别取n+1个点然后对应相乘，此时只相乘了n+1次就可得到n+1个点，从而确定两个多项式相乘结果的多项式，并且计算的复杂度为o(n)。
所以现在我们的思路就是通过两个多项式A、B的系数，然后从两个多项式中取点，求出点的值，然后根据求出来的值和取的点反推回C的系数，就这样多项式相乘的结果就出来了。那么在求值的过程中就是FFT要做的事情（卷积过程），在反推系数的过程中就是IFFT做的事情（卷积逆运算）。
那么是不是在计算C(x)=A(x)*B(x)时，就从A(x)和B(x)取n+1个x带入到A(x)与B(x)中然后求出n+1个点相乘？
当然不是这么简单的去取点，如果这样做的话最终复杂度还是o()，因为每个点的计算复杂度都是o(n)，然后又有n个点，最终复杂度还是 o()。
2.怎么取点
如果要计算n个点的值，我们是否需要取n个点，然后求n次值呢，当然是不需要的，从下图可以看出，当点具有奇偶性时我们就只需要取一半的点就可以得到所有的值。
所以根据以上的理论基础我们可以先将一个多项式的奇数项写一起，偶数项写一起：
所以：
如果我们有n-1阶多项式需要取n个点，那么根据奇偶性我们只需要取n/2-1个点，而每部分都是n/2-1阶。现在变成求 n/2-1个点的n/2-1 阶的多项式的值， 那么我们又怎么求这 n/2-1 阶的多项式的值呢，当然还是用同样的方法，再把关于x^2的多项式根据奇偶拆分，一直拆分.........，一直分到最后只求1个点的值，因为一个点的值比较好算，所以我们得到一个点的值再反推回去，那么就可以得到n个点开n次方的值，就可以得到这个多项式的n个点所有值了。
到这里之后就很像是递归的算法了，但是目前还有一个问题就是第一次分奇偶自变量可以取±x得出来A(x),A(-x),然而在第二次分的时候原式子中全是x^2的多项式怎么能将自变量取成一正一负的形式呢，所以为了使得递归成立，FFT引入了复数，如果令x1=1的话：
可见有了复数的加入递归算法就成立了，那么整个计算的复杂度为o(nlogn)，因为一直在做对半分的操作，所以在取FFT的点数的时候尽量取2^n个，对于不够的则补零。也可以看出我们所需要取的点就是1开n次方后的n个值，我们要求这n个值是n/2对相反数。
3.单位根
由上文我们知道需要取的点就是1开n次方后呈互为相反数的n个点，所以FFT又引入了单位圆复平面，因为1的n次方根可以解释为复平面上沿着单位圆等距排布的一系列点。
设幅角为正且最小的复数为
,这就是n次单位根，表达式为（由欧拉公式推）：
而所有的单位根的表达式为：
单位根有一些性质：
（1）折半引理
（2）
（3）加法引理
（4）消去引理
由上式（1）可见在单位圆上所有的点的取值都有存在其相反数，点平方后还是和原复数相等，当单位圆上的点平方后点数减半，但依旧满足所有点存在相反数。
4.FFT实现
以上的单位根的性质正好满足咱们所需要的点的要求，所以将所取的点换成
。
那么此时第一部分多项式：
折半引理后：
![A(\omega _{n}^{k})=A_{1}(\omega _{\frac{n}{2}}^{k})+\omega _{n}^{k}A_{2}(\omega _{\frac{n}{2}}^{k}) , k\epsilon [0,\frac{n}{2}-1]](https://img2.php1.cn/3cdc5/3984/ae9/74719cd91795d250.gif)
第二部分多项式：
折半引理后：
![A(\omega _{n}^{k})=A_{1}(\omega _{\frac{n}{2}}^{k})-\omega _{n}^{k}A_{2}(\omega _{\frac{n}{2}}^{k}) , k\epsilon [\frac{n}{2},n-1]](https://img2.php1.cn/3cdc5/3984/ae9/1243fcfc0db0e515.gif)
最后不断递归就可以求出最终的值了，这个过程也就是FFT变换。
5.IFFT变换
FFT变换就是快速的DFT变换，DFT变换时是由一个多项式系数矩阵乘以DFT变换矩阵得到的一堆多项式值的矩阵。FFT则是当
(
)时的变换。
而IFFT则是跟FFT一样的原理，此时我们需要根据给出的多项式值求出多项式系数，将DFT变换矩阵求逆，然后乘上值向量最终得到多项式系数矩阵。而且在对DFT矩阵求逆后矩阵里的
（
）,那么我们就可以使用FFT同样的方式来进行IFFT变换了。
以上分享均是自己在学习时的笔记，相关视频链接发出来被和谐，自行上某站搜索FFT 。
如有侵权，请联系我删除哈~~~~
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有