十分简明易懂的FFT（快速傅里叶变换）

快速傅里叶变换 (Fast Fourier Transform, 简称 FFT) 是离散傅里叶变换 (DFT) 的一种快速、高效的算法。它由 J.W. Cooley 和 T.W. Tukey 在 1965 年提出。

在处理多项式乘法（或卷积）时，朴素的高精度乘法需要$O(n^2)$ 的时间复杂度。而 FFT 巧妙地利用了离散傅氏变换的奇偶、虚实等特性，能将时间复杂度大幅优化至$O(n \log_2 n)$。被变换的抽样点数$N$ 越多，FFT 算法计算量的节省就越显著。

一、 多项式的两种表示法

FFT 的核心思想是：用$O(n \log_2 n)$ 的时间将一个用系数表示的多项式转换成它的点值表示，完成乘法后再转换回来。

1.1 系数表示法

一个$n-1$ 次$n$ 项多项式$f(x)$ 可以表示为：

也可以直接用每一项的系数集合来表示：

1.2 点值表示法

如果把多项式放到平面直角坐标系里面看成一个函数，代入$n$ 个不同的$x$，会得出$n$ 个不同的$y$。

这$n$ 个点可以唯一确定该多项式（即有且仅有一个$n-1$ 次多项式满足$\forall k, f(x_k) = y_k$，相当于解$n$ 元一次方程组）。因此，$f(x)$ 还可以表示为：

这就是点值表示法。

1.3 乘法复杂度的区别

• 系数表示法： 若将多项式$A(x)$ 和$B(x)$ 相乘，需要枚举$A$ 每一位的系数与$B$ 每一位的系数相乘，时间复杂度为$O(n^2)$。

• 点值表示法： 若两者的点值表示在相同的$x_i$ 处取值，它们相乘后的多项式$h(x)$ 的点值只需将对应的纵坐标直接相乘：

  $$h(x) = \{(x_0, f(x_0) \cdot g(x_0)), \cdots, (x_{n-1}, f(x_{n-1}) \cdot g(x_{n-1}))\}$$

  这个过程只需要枚举一次，时间复杂度仅为$O(n)$。

概念明确： 朴素的系数转点值的算法叫 DFT（离散傅里叶变换），点值转系数叫 IDFT（离散傅里叶逆变换）。

二、 前置知识：复数与单位根

2.1 复数基础

我们把形如$z = a + bi$（$a,b \in \mathbb{R}$）的数称为复数，其中$a$ 为实部， $b$为虚部，$i$ 为虚数单位。

定义$i^2 = -1$，引入复数后就可以表示负数的平方根，如$\sqrt{-7} = \sqrt{7}i$。

• 复平面： 复数可以看作复平面直角坐标系上的一个点$(a,b)$ 或代表它的向量。

• 模长： 复数$z$ 到原点的距离，记为$|z| = \sqrt{a^2 + b^2}$。

• 共轭复数：$z = a + bi$ 的共轭复数为$\overline{z} = a - bi$（即虚部取反）。

2.2 复数的运算性质

• 加法：$(a + bi) + (c + di) = (a + c) + (b + d)i$（满足向量的平行四边形法则）。

• 乘法：$(a + bi) \cdot (c + di) = (ac - bd) + (ad + bc)i$。

• 乘法的几何意义（极其重要）： 模长相乘，极角相加。

  $$(a_1, \theta_1) \cdot (a_2, \theta_2) = (a_1 a_2, \theta_1 + \theta_2)$$

  复数相加也满足平行四边形法则即 A B + A D = A C

  复数相乘还有一个值得注意的小性质： 模长相乘，极角相加

• 

  

  

三、 DFT 与 FFT 核心解析

(注：从这里开始，所有的项数$n$ 都默认为$2$ 的整数次幂)

3.1 离散傅里叶变换 (DFT) 与 单位根$\omega$

任意取$n$ 个$x$ 值代入计算多项式，暴力计算$x_k^0, x_k^1, \cdots, x_k^{n-1}$ 依然需要$O(n^2)$ 的时间。

傅里叶提出，代入单位圆上的等分点可以极大简化运算。以半径为$1$ 的单位圆为例，将其$n$ 等分，从$(1,0)$ 开始逆时针标号。第$k$ 个点代表的复数称为$n$ 次单位根，记为$\omega_n^k$：

结合欧拉公式$e^{ix} = \cos x + i \sin x$（特例：$e^{i\pi} + 1 = 0$ ），单位根具有以下优秀性质，这也是推导 FFT 分治的基础：

1. 折半引理：$\omega_n^k = \omega_{2n}^{2k}$ （两者表示的复数点相同）。

2. 对称引理：$\omega_n^{k + n/2} = -\omega_n^k$ （在单位圆上关于原点对称）。

3. 周期性：$\omega_n^0 = \omega_n^n = 1$。

3.2 快速傅里叶变换 (FFT) 的分治思想

DFT 仍然是暴力的$O(n^2)$，但通过单位根的性质，我们可以利用分治对其进行优化。

设多项式$A(x) = a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1}$。

按$A(x)$ 下标的奇偶性将其分成两半，并在奇数部分提一个$x$ 出来：

设两个新多项式：

$A_1(x) = a_0 + a_2x + \cdots$

$A_2(x) = a_1 + a_3x + \cdots$

则有原多项式重组公式：$A(x) = A_1(x^2) + xA_2(x^2)$

将$\omega_n^k$ ($k < n/2$ ) 代入上式：

利用对称引理，将另一半$\omega_n^{k + n/2}$ 代入：

核心结论：

计算$A(\omega_n^k)$ 和$A(\omega_n^{k + n/2})$ 时，公式的后半段只有符号不同！

这意味着，在分治回溯时，我们只要知道前一半序列$A_1(\omega_{n/2}^k)$ 和$A_2(\omega_{n/2}^k)$ 的值，就可以直接算出后一半序列的答案。

每次递归一分为二，当$n=1$ 时只有一个常数项直接 return。这成功将时间复杂度降到了$O(n \log_2 n)$。

3.3 快速傅里叶逆变换 (IFFT)

计算完卷积后，我们需要将点值表示的多项式转回系数表示。

如果用普通的 IDFT 暴力解依然是$O(n^2)$。如何使用 FFT 的框架在$O(n \log_2 n)$ 内解决？

数学推导表明： 将多项式在分治的过程中，乘上的单位根全部替换为其共轭复数$\omega_n^{-k}$ 进行同样的 FFT 操作。分治完成后，将得到的每一项结果除以$n$，即为原多项式的每一项系数。