参考：快速傅里叶变换(FFT)——历史上最巧妙的算法？ 参考:傅里叶快速变换:（FFT）超详解 傅里叶快速变换 (Fast Fourier Transform)，即使用计算机计算离散傅里叶的转换（DFT）高效快速计算方法的总称，简称FFT，于1965年由J.W.库利和T.W.图基提出。 
总结：FFT算法的计算速度大大加快，时间复杂度降低到数量级。
FFT的思想
将多项式表示为多项式乘积，然后分为奇数项和偶数项的乘积。然后将奇数项拆除X表示 用上半部分单位的单位根 w n k w^{k}_{n} wnk来表示 x 2 x^{2} x2。
1.多项系数和点值表示
2、单位根
2、IDFT
跑完FFT之后，我们得到了多项乘积的点值表示。现在我们需要表示点值表示转回系数。这种转换过程称为离散傅里叶逆变（IDFT）。
参考:彻底了解傅里叶快速变换FFT核心思想–分而治之
显然没那么简单。试着计算下一个组合索引是4和12的点对。一眼就能看出，根据DFT该公式的频率为1，重量结果为0，与上述蝴蝶操作不一致a2= x4 x因此，这种重复操作不能简单地完成。
为了解决这个问题，平移信号，即让它只是在4和12是1或1，这只是改变原始信号的相位，同时使用蝴蝶操作实现这个简单的重复计算，另一个问题是原始信号改变，如何保持最终计算不变，下一篇文章介绍旋转因子来解决信号平移的问题。 在最后一篇文章中，引入蝴蝶操作来计算样本对DFT，实现了分而治之中简单重复小块的处理，引入了信号相位变化的新问题。为了保持整体结果不变，平移后的信号被用作下一阶段的输入。 根据分而治之的思想，我们已经完成了DIVIDE和CONQUER阶段，下一步需要COMBINE，即将样本对的计算结果组合成新的样本对。根据样本对的计算顺序，将两点样本对集合成四点样本对。根据我们所说的四个样本点的信号DFT原理，4点是测试4个频率，我们之前计算过0和1hz组合频率分量需要额外计算2和3hz根据我们在第一篇文章核心思想中的频率分量–正余弦函数的周期性，每隔2次hz所测试的余弦波的值是相等的，也就是 0hz和2hz计算结果相同，1和3Hz的结果一样
计算0和8， 4和12这四点频率为0DFT结果，直接a0 a2就结束了，但我们以前a现在乘以信号的相位W40的旋转因子将他转换回来，然后加起来得到b0, 4点样本信号的频率为0DFT同样，我们计算结果b1,b2,b3
每个 4 点蝶形包含两个旋转因子，所以每个 8 点蝶形包含四个旋转因子。在 FFT 旋转因子的数量必须是盘中点数的一半。在 FFT 算法的 2 点蝶形阶段，如样本4和12信号，产生平移位置a2和a3 。在 4 点蝶形阶段，通过旋转因子将其移回正确的位置b2到b3。在这 4 点在原始位置，即b0到b不需要相位因子。 但样本点2、10、6、14对应2点蝶形结果a4,a5,a6,a7 ，当它们到达 4 点蝴蝶的输出时仍然没有回到原来的位置。这是因为由于它们在信号中的位置，被 2 点蝶操作平移了太多距离。因此，在 8 在蝴蝶中，它们需要额外的旋转因子来进一步将它们移回原位。
最后将8个点组合成16个点，大功告成。这是蝴蝶操作汇总图的原始信号16个点和16个频率。到目前为止，FFT计算结束了，但我们得到了什么结果，如何分析呢？
到目前为止，我们已经完全解释了整个过程FFT算法的过程，现在以前的计算结果汇总成一张表格，共16行，对应16个频率的傅里叶级数，其中x是原始信号点，a是2点蝶形操作的结果，b是4点蝶形，c是8点蝶形 ，d这是蝴蝶16点操作的结果，也是我们需要的FFT因此，一组复数类似如下： 根据我们之前的例子，总共测试了16个频率，然后得到了16组复数，最后计算了正弦波的特性：频率、范围和相位，可以制作相应的频谱图、相位图等
由于将复杂的(周期)信号分解为正弦波，傅里叶变换是一种非常强大的工具。FFT 这是计算机计算傅里叶转换的一种非常有效的方法。蝴蝶操作方便计算机重复和简单操作。在这里，傅里叶的所有相关文章都结束了。