什么是快速傅里叶变换（Fast Fourier Transform, FFT）
度数为 $ n $ 的多项式 $ P(x) $ 可以表示为：
$$ P(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \ldots + a_nx^n $$
可以采用系数表示法，即：
$$ a_0, a_1, a_2, \ldots, a_n $$
也可以采用点值表示法，即：
$$ (x_0,y_0), (x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n) $$
FFT 是将系数表示转为点值表示的算法。
分治算法
- 将多项式 $ P(x) $ 分为奇数项和偶数项，$ x \in X $：
$$ P_{\text{odd}} = a_1x + a_3x^2 + \ldots + a_{n-1}x^{n-1} \quad \text{(度数为 $ n/2 $)} $$ $$ P_{\text{even}} = a_0 + a_2x^2 + \ldots + a_{n-2}x^{n-2} \quad \text{(度数为 $ n/2 $)} $$ $$ P(x) = P_{\text{odd}}(x^2) + xP_{\text{even}}(x^2) \quad \text{(总多项式)} $$
- 递归地计算 $ P_{\text{odd}}(x^2) $ 和 $ P_{\text{even}}(x^2) $
- 组合
时间复杂度分析
观察 1: 拆分多项式
在拆分多项式为奇数次项和偶数次项时，我们需要遍历所有的 $ a_i $ 系数。这个操作的时间复杂度是 $ O(n) $。
观察 2: 点的数量
在算法开始时，输入点集 $ X $ 的大小与多项式 $ P(x) $ 的度数相同，即 $ |X| = n $。值得注意的是，在递归步骤中，即便 $ P(x) $ 的度数减半���输入点集的大小依然保持不变。这是因为在计算 $ P_{\text{odd}}(x^2) $ 和 $ P_{\text{even}}(x^2) $ 时，我们依然需要在同样的点集 $ X $ 上进行评估。
观察 3: 递归复杂度
递归地计算 $ P_{\text{odd}}(x^2) $ 和 $ P_{\text{even}}(x^2) $ 会生成两个子问题，每个子问题的大小是原问题大小的一半。因此，递归的时间复杂度为 $ 2T(n/2, |X|) $。
观察 4: 组合结果的复杂度
根据 $ P(x) = P_{\text{odd}}(x^2) + xP_{\text{even}}(x^2) $，我们需要对每个 $ x $ 值进行一次乘法和一次加法以得到 $ P(x) $ 的值。这一步的时间复杂度是 $ O(|X|) $。 同时可以看到最开始 $ |X| = n $。
综合以上观察，我们可以得出总体时间复杂度公式为：
$$ T(n, |X|) = 2T\left(\frac{n}{2}, |X|\right) + O(n + |X|) $$
由于二叉树的高度为 $ \log_2 n $，最后一层有 $ n $ 个节点，每个节点需要 $ O(n) $ 的时间来完成计算（主要是由于观察 4 的组合结果步骤），因此总体时间复杂度为 $ O(n^2) $。
优化
现在主要的问题是： $$ |X| = |X^2| = |X^4| $$ 我们希望： $$ |X| = 2 \times |X^2| = 2^2 \times |X^4| = \ldots = 2^{\log n} \times 1 $$
正负数
当我们输入： $$ S = \{+1，-1\} $$ 时，我们可以得��： $$ S^2 = \{+1，-1\}^2 = \{+1\} $$ 看似满足了第一步，但是无法进行下一次递归，也就是说之后的时间复杂度还是 $ O(n^2) $。
虚数
$ x^n = 1 $ 的解为： $$ \omega^0,\omega^1, \ldots ,\omega^{n-1}, \quad \omega = e^{2\pi i/n} \text{ 有 $ n $ 个解 } $$ 证明： 已知：欧拉公式： $$ e^{\pi i} = -1 $$ 则： $$ (\omega^k)^n = (\omega^n)^k = (e^{2\pi i})^k = (-1)^{2k} = 1 $$ $ i $ 是虚数单位。
也就是说，我们可以用复数来表示 $ x $。这样， $$ |X| = 2 \times |X^2| = 2^2 \times |X^4| = \ldots = 2^{\log n} \times 1 $$
证明： $$ x^n = (x^2)^{n/2} = 1 $$ 则： $$ |X| = 2 \times |X^2| $$
最后的时间复杂度
最终，我们可以得到： $$ T(n, |X|) = 2T\left(\frac{n}{2}, |X|\right) + O(n + |X|)\quad \text{($ |X| $ 会随 $ n $ 的减小而减小)} $$ 即 $$ T(n) = 2T(\frac{n}{2}) + O(n) = O(n\log n) $$ 总体时间复杂度为 $ O(n\log n) $。
