快速傅里叶变换（The Fast Fourier Transform，FFT）

快速傅里叶变换

本篇博客所整理的内容参考资料如下：

资料出处1：The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

资料出处2：FFT

资料出处3：多项式求值和插值，单位方根

基础知识介绍：
离散傅里叶（Discrete Fourier Transform，DFT）矩阵实现时域与频域之间的转换

以下图表源自：[傅里叶分析之掐死教程（完整版）更新于2014.06.06](https://zhuanlan