Fast Fourier Transform (FFT) includes a reference graph.

快速傅里叶变化（FFT）含模板

• 快速傅里叶变化（FFT）

• • 前置知识索引

  • • 复数 Complex Number

    • 单位根

    • • 单位根-三个引理

    • 多项式

    • • 多项式加法

  • 多项式乘法

  • 系数表示

  • 点值表示

  • DFT以及FFT原理推导

  • • 离散傅里叶变换（Discrete Fourier Transform）
    • 快速傅里叶变换（Fast Fourier Transform）

  • 递归代码实现

  • 通过位逆序置换的优化代码实现

快速傅里叶变化（FFT）

资料来源：https://www.bilibili.com/video/BV1Y7411W73U

前置知识索引

FFT的核心算法逻辑深深植根于复数运算与单位根的代数性质之中。在算法竞赛及高性能计算领域，FFT最典型且广泛的应用场景是高效计算多项式乘法，这在数学上等价于执行两个序列的线性卷积。理解这一过程，不仅需要扎实的代数基础，更需对离散信号处理中的频域变换有直观认识。

复数 Complex Number

在深入探讨FFT之前，我们必须首先夯实复数这一数学基石。复数不仅仅是实数的扩展，它在几何与代数