cover.png#快速傅里叶变换

快速傅里叶变换 (Fast Fourier Transform, FFT) 是一种高效计算离散傅里叶变换 (Discrete Fourier Transform, DFT) 的分治算法

在算法课中，FFT 作用是把两个次数界为 \(n\) 的多项式乘法从朴素的 \(O(n^2)\) 降到：

\[ O(n\log n) \]

更一般地，FFT 可以快速计算卷积，因此也会出现在整数乘法、字符串匹配、模式匹配、信号处理等问题中

多项式乘法

设有两个多项式：

\[ A(x)=a_0+a_1x+\cdots+a_{n-1}x^{n-1} \]

\[ B(x)=b_0+b_1x+\cdots+b_{n-1}x^{n-1} \]

它们的乘积为：

\[ C(x)=A(x)B(x)=c_0+c_1x+\cdots+c_{2n-2}x^{2n-2} \]

其中第 \(i\) 项系数为：

\[ c_i=\sum_{k=0}^{i}a_kb_{i-k} \]

这里默认越界的系数为 \(0\)

这个公式就是卷积。若直接按照定义计算，每个 \(a_k\) 都可能与每个 \(b_j\) 相乘，运行时间为：

\[ O(n^2) \]

---

多项式的两种表示

系数表示

系数表示就是直接保存：

\[ (a_0,a_1,\ldots,a_{n-1}) \]

这种表示下：

• 多项式加法很容易，逐项相加即可，时间 \(O(n)\)
• 多项式在单点求值可以用 Horner 法，时间 \(O(n)\)
• 多项式乘法朴素做法需要 \(O(n^2)\)

Horner 法可以写成：

\[ A(x_0) =a_0+x_0(a_1+x_0(a_2+\cdots+x_0a_{n-1})\cdots) \]

它只需要线性次乘加

点值表示

一个次数界为 \(n\) 的多项式也可以用 \(n\) 个点值对表示：

\[ \{(x_0,y_0),(x_1,y_1),\ldots,(x_{n-1},y_{n-1})\} \]

其中 \(x_0,x_1,\ldots,x_{n-1}\) 两两不同，并且：

\[ y_k=A(x_k) \]

\(n\) 个互不相同点上的取值可以唯一确定一个次数界为 \(n\) 的多项式

这个结论可以从范德蒙德矩阵看出来。把求值关系写成矩阵：

\[ \begin{bmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^{n-1}\\ 1 & x_1 & x_1^2 & \cdots & x_1^{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1} \end{bmatrix} \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{n-1} \end{bmatrix} = \begin{bmatrix} y_0\\ y_1\\ \vdots\\ y_{n-1} \end{bmatrix} \]

左边矩阵是范德蒙德矩阵。它的行列式为：

\[ \prod_{0\leq j<k\leq n-1}(x_k-x_j) \]

只要所有 \(x_k\) 互不相同，行列式就非零，因此矩阵可逆，系数唯一存在

点值表示下的乘法

如果：

\[ C(x)=A(x)B(x) \]

那么对任意点 \(x_k\) 都有：

\[ C(x_k)=A(x_k)B(x_k) \]

也就是说，在相同求值点上，只要逐点相乘就可以得到乘积多项式的点值表示。

但有一个次数问题：若 \(A\) 和 \(B\) 的次数界都是 \(n\)，则 \(C\) 的次数界是 \(2n-1\) 或 \(2n\) 量级，为了唯一确定 \(C\)，需要至少 \(2n-1\) 个点值，实际算法中通常取一个方便的长度 \(N\geq 2n-1\)

因此，用点值表示做多项式乘法的思路是：

1. 把 \(A,B\) 从系数表示转换为点值表示
2. 逐点相乘
3. 把乘积从点值表示插值回系数表示

如果第一步和第三步都能在 \(O(n\log n)\) 时间内完成，总乘法就能达到 \(O(n\log n)\)

FFT 的作用是高效完成这两种表示之间的转换

---

单位复数根

FFT 的特殊求值点来自单位复数根

定义

\(n\) 次单位复数根是满足：

\[ \omega^n=1 \]

的复数。它们一共有 \(n\) 个，均匀分布在复平面的单位圆上：

\[ 1,\omega_n,\omega_n^2,\ldots,\omega_n^{n-1} \]

其中：

\[ \omega_n=e^{2\pi i/n} \]

称为主 \(n\) 次单位根。

由欧拉公式：

\[ e^{i\theta}=\cos\theta+i\sin\theta \]

可知：

\[ \omega_n=\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n} \]

消去性质

对任意正整数 \(d\)，有：

\[ \omega_{dn}^{dk}=\omega_n^k \]

因为：

\[ \omega_{dn}^{dk} =\left(e^{2\pi i/(dn)}\right)^{dk} =e^{2\pi ik/n} =\omega_n^k \]

这个性质说明，高阶单位根的某些幂会退化成低阶单位根

折半性质

当 \(n\) 为偶数时，\(n\) 个 \(n\) 次单位根的平方正好是 \(n/2\) 个 \(n/2\) 次单位根，并且每个出现两次：

\[ (\omega_n^k)^2=\omega_n^{2k}=\omega_{n/2}^k \]

并且：

\[ (\omega_n^{k+n/2})^2 =\omega_n^{2k+n} =\omega_n^{2k} \]

FFT 分治正是利用这个性质：把 \(n\) 个求值点平方后，只剩下 \(n/2\) 个不同的求值点

求和性质

\[ \sum_{j=0}^{n-1}\omega_n^{jk} = \begin{cases} n & n\mid k\\ 0 & n\nmid k \end{cases} \]

当 \(n\nmid k\) 时，这是等比数列：

\[ \sum_{j=0}^{n-1}\omega_n^{jk} =\frac{1-(\omega_n^k)^n}{1-\omega_n^k} =0 \]

因为 \((\omega_n^k)^n=1\)，但 \(\omega_n^k\neq 1\)

---

DFT

给定系数向量：

\[ a=(a_0,a_1,\ldots,a_{n-1}) \]

定义多项式：

\[ A(x)=\sum_{j=0}^{n-1}a_jx^j \]

它的离散傅里叶变换 DFT 是向量：

\[ y=(y_0,y_1,\ldots,y_{n-1}) \]

其中：

\[ y_k=A(\omega_n^k) =\sum_{j=0}^{n-1}a_j\omega_n^{jk}, \qquad 0\leq k<n \]

所以 DFT 本质上就是把多项式 \(A(x)\) 在 \(n\) 个单位复数根处求值

用矩阵表示：

\[ \begin{bmatrix} y_0\\ y_1\\ \vdots\\ y_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \omega_n & \omega_n^2 & \cdots & \omega_n^{n-1}\\ 1 & \omega_n^2 & \omega_n^4 & \cdots & \omega_n^{2(n-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \omega_n^{n-1} & \omega_n^{2(n-1)} & \cdots & \omega_n^{(n-1)(n-1)} \end{bmatrix} \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_{n-1} \end{bmatrix} \]

这仍然是一个范德蒙德矩阵，只是求值点被固定为：

\[ 1,\omega_n,\omega_n^2,\ldots,\omega_n^{n-1} \]

朴素计算这个矩阵乘法需要：

\[ O(n^2) \]

FFT 的目标是把它降到：

\[ O(n\log n) \]

---

FFT 的分治思想

设 \(n\) 是 \(2\) 的幂。把多项式按系数下标奇偶拆成两部分：

\[ A^{[0]}(x)=a_0+a_2x+a_4x^2+\cdots+a_{n-2}x^{n/2-1} \]

\[ A^{[1]}(x)=a_1+a_3x+a_5x^2+\cdots+a_{n-1}x^{n/2-1} \]

则：

\[ A(x)=A^{[0]}(x^2)+xA^{[1]}(x^2) \]

现在要计算：

\[ A(\omega_n^0),A(\omega_n^1),\ldots,A(\omega_n^{n-1}) \]

代入上式：

\[ A(\omega_n^k) =A^{[0]}((\omega_n^k)^2)+\omega_n^kA^{[1]}((\omega_n^k)^2) \]

由于：

\[ (\omega_n^k)^2=\omega_{n/2}^k \]

因此只需要递归地把 \(A^{[0]}\) 和 \(A^{[1]}\) 在 \(n/2\) 个 \(n/2\) 次单位根处求值

合并公式

令：

\[ y_k^{[0]}=A^{[0]}(\omega_{n/2}^k) \]

\[ y_k^{[1]}=A^{[1]}(\omega_{n/2}^k) \]

对 \(0\leq k<n/2\)，有：

\[ y_k=A(\omega_n^k) =y_k^{[0]}+\omega_n^k y_k^{[1]} \]

同时：

\[ y_{k+n/2}=A(\omega_n^{k+n/2}) \]

注意：

\[ \omega_n^{k+n/2} =\omega_n^k\omega_n^{n/2} =-\omega_n^k \]

而：

\[ (\omega_n^{k+n/2})^2=(\omega_n^k)^2 \]

所以：

\[ y_{k+n/2} =y_k^{[0]}-\omega_n^k y_k^{[1]} \]

因此一次递归得到两个长度为 \(n/2\) 的 DFT 后，只需要 \(O(n)\) 时间就能合并成长度为 \(n\) 的 DFT

---

递归 FFT

递归算法可以写成：

RECURSIVE-FFT(a)
    n = a.length
    if n == 1
        return a

    omega_n = exp(2*pi*i/n)
    omega = 1

    a_even = (a_0, a_2, ..., a_{n-2})
    a_odd  = (a_1, a_3, ..., a_{n-1})

    y_even = RECURSIVE-FFT(a_even)
    y_odd  = RECURSIVE-FFT(a_odd)

    for k = 0 to n/2 - 1
        y_k       = y_even_k + omega * y_odd_k
        y_{k+n/2} = y_even_k - omega * y_odd_k
        omega = omega * omega_n

    return y

时间复杂度

每一层递归做两次规模为 \(n/2\) 的 FFT，再做 \(O(n)\) 的合并：

\[ T(n)=2T(n/2)+O(n) \]

由主定理得到：

\[ T(n)=O(n\log n) \]

递归树也可以直观看出这一点：

• 第 \(0\) 层总规模 \(n\)
• 第 \(1\) 层两个子问题，总规模仍为 \(n\)
• 第 \(2\) 层四个子问题，总规模仍为 \(n\)
• 一共有 \(\log n\) 层

所以总时间为：

\[ O(n\log n) \]

关于 \(n\) 是 \(2\) 的幂

上面的递归 FFT 假设 \(n\) 是 \(2\) 的幂

在多项式乘法中，这通常不是问题：可以把系数向量补零到不小于结果长度的下一个 \(2\) 的幂

例如两个长度为 \(n\) 的系数向量相乘，结果长度最多为 \(2n-1\)，可以取：

\[ N=2^{\lceil \log_2(2n-1)\rceil} \]

然后把两个输入都补到长度 \(N\)

但需要注意，这不是说“任意长度的 DFT 都可以无损地当作长度为 \(2\) 的幂”

假设 \(n\) 是 \(2\) 的幂并不是完全不失一般性。对任意长度 DFT，需要更一般的 FFT 变体或不同的分解方法；只是对本节的多项式乘法应用，补零已经足够

---

逆 DFT

DFT 把系数向量 \(a\) 变成点值向量 \(y\)，逆 DFT 要做相反的事：给定：

\[ y_0,y_1,\ldots,y_{n-1} \]

恢复：

\[ a_0,a_1,\ldots,a_{n-1} \]

由上面的矩阵变换得：

\[ a_j=\frac{1}{n}\sum_{k=0}^{n-1}y_k\omega_n^{-jk} \]

也就是说，逆 DFT 与 DFT 几乎一样，只需要把 \(\omega_n\) 换成 \(\omega_n^{-1}\)，最后再除以 \(n\)

公式证明

把 \(y_k\) 展开：

\[ \begin{aligned} \frac{1}{n}\sum_{k=0}^{n-1}y_k\omega_n^{-jk} &= \frac{1}{n}\sum_{k=0}^{n-1} \left(\sum_{\ell=0}^{n-1}a_\ell\omega_n^{\ell k}\right) \omega_n^{-jk}\\ &= \frac{1}{n}\sum_{\ell=0}^{n-1}a_\ell \sum_{k=0}^{n-1}\omega_n^{(\ell-j)k} \end{aligned} \]

由单位根求和性质：

\[ \sum_{k=0}^{n-1}\omega_n^{(\ell-j)k} = \begin{cases} n & \ell=j\\ 0 & \ell\neq j \end{cases} \]

所以最后只剩下：

\[ a_j \]

因此逆 DFT 的公式成立

用 FFT 计算逆 DFT

逆 DFT 可以直接复用 FFT 框架：

INVERSE-FFT(y)
    run FFT on y using omega_n^{-1}
    divide every output by n

时间复杂度仍然是：

\[ O(n\log n) \]

---

FFT 多项式乘法

现在可以把前面的内容组合起来

输入：

\[ A(x)=\sum_{i=0}^{n-1}a_ix^i \]

\[ B(x)=\sum_{i=0}^{n-1}b_ix^i \]

目标是输出：

\[ C(x)=A(x)B(x) \]

算法：

FFT-POLYNOMIAL-MULTIPLY(a, b)
    N = the smallest power of 2 with N >= len(a) + len(b) - 1

    pad a and b with zeros to length N

    A = FFT(a)
    B = FFT(b)

    for k = 0 to N - 1
        C_k = A_k * B_k

    c = INVERSE-FFT(C)

    return c_0, c_1, ..., c_{len(a)+len(b)-2}

正确性

补零后，\(A\) 和 \(B\) 都被看成次数界为 \(N\) 的多项式。由于：

\[ N\geq \deg(A)+\deg(B)+1 \]

乘积 \(C\) 的系数可以被长度 \(N\) 的向量完整容纳

FFT 求出的是：

\[ A(\omega_N^k),\quad B(\omega_N^k) \]

逐点相乘得到：

\[ A(\omega_N^k)B(\omega_N^k)=C(\omega_N^k) \]

也就是 \(C\) 在 \(N\) 个不同单位根处的点值表示

由于次数界为 \(N\) 的多项式由 \(N\) 个不同点值唯一确定，逆 DFT 插值回来的系数就是 \(C(x)\) 的系数

复杂度

算法包含：

• 两次 FFT：\(2O(N\log N)\)
• 一次逐点相乘：\(O(N)\)
• 一次逆 FFT：\(O(N\log N)\)

所以总时间为：

\[ O(N\log N) \]

当 \(N=O(n)\) 时：

\[ O(n\log n) \]

空间复杂度通常为：

\[ O(N) \]

若递归实现中频繁复制数组，实际可能产生额外空间；工程实现中通常使用迭代原地 FFT

---

卷积

对两个序列：

\[ a=(a_0,a_1,\ldots,a_{n-1}) \]

\[ b=(b_0,b_1,\ldots,b_{m-1}) \]

它们的线性卷积定义为：

\[ (a*b)_t=\sum_i a_i b_{t-i} \]

其中越界项视为 \(0\)

如果构造多项式：

\[ A(x)=\sum_i a_ix^i,\qquad B(x)=\sum_i b_ix^i \]

那么：

\[ A(x)B(x)=\sum_t (a*b)_t x^t \]

所以卷积就是多项式乘法的系数

因此，FFT 可以在：

\[ O((n+m)\log(n+m)) \]

时间内计算线性卷积

线性卷积和循环卷积

DFT 本身天然对应长度为 \(N\) 的循环卷积

如果不补零，超过 \(N-1\) 次的高次项会折回低次项，相当于在模 \(x^N-1\) 意义下相乘

为了得到普通的线性卷积，必须取：

\[ N\geq n+m-1 \]

并把两个序列都补零到长度 \(N\)

这也是多项式乘法算法中要先补零的原因

---

应用一：二进制串中的三等距 1

问题

给定长度为 \(n\) 的二进制串 \(S\)，记：

\[ L=\{i:S[i]=1\} \]

判断是否存在三个位置：

\[ a<b<c \]

满足：

\[ S[a]=S[b]=S[c]=1 \]

并且三者等距：

\[ b-a=c-b \]

等价地：

\[ a+c=2b \]

例如：

• 11100000 中有位置 \(0,1,2\)
• 110110010 中有位置 \(1,4,7\)
• 1011 中没有三个等距的 \(1\)

朴素算法

直接枚举起点 \(i\) 和间距 \(d\)：

\[ i,\ i+d,\ i+2d \]

检查这三个位置是否都是 \(1\)

起点和间距各有 \(O(n)\) 种，时间复杂度为：

\[ O(n^2) \]

卷积算法

构造多项式：

\[ P(x)=\sum_{i\in L}x^i \]

计算：

\[ Q(x)=P(x)^2 \]

设：

\[ Q(x)=\sum_t q_tx^t \]

则 \(q_t\) 表示有多少个有序对 \((a,c)\) 满足：

\[ a,c\in L,\qquad a+c=t \]

现在固定一个中点 \(b\in L\)。如果存在 \(a,c\in L\) 使得：

\[ a+c=2b,\qquad a\neq c \]

那么：

\[ a,b,c \]

就是三个等距的 \(1\)

为什么检查 \(q_{2b}\geq 3\)？

• 对 \((b,b)\)，一定贡献 \(1\)
• 如果存在 \(a\neq c\) 且 \(a+c=2b\)，那么 \((a,c)\) 和 \((c,a)\) 会再贡献 \(2\)

所以：

\[ q_{2b}\geq 3 \]

当且仅当存在以 \(b\) 为中点的非平凡等距三元组

算法：

THREE-EVENLY-SPACED-ONES(S)
    L = {i : S[i] = 1}
    build P(x) = sum_{i in L} x^i
    Q = P * P using FFT

    for each b in L
        if coefficient Q[2b] >= 3
            return YES

    return NO

构造和扫描是 \(O(n)\)，FFT 乘法是 \(O(n\log n)\)，所以总时间为：

\[ O(n\log n) \]

---

应用二：字符串匹配

问题

给定文本：

\[ t[0],t[1],\ldots,t[n-1] \]

和模式串：

\[ p[0],p[1],\ldots,p[m-1] \]

目标是找所有位移 \(i\)，使得：

\[ t[i+j]=p[j],\qquad 0\leq j<m \]

也就是：

\[ t[i:i+m-1]=p \]

朴素算法对每个位置比较 \(m\) 个字符，最坏时间为：

\[ O(nm) \]

如果把字符编码为数字，可以用卷积一次性计算所有位置的匹配分数。

匹配分数

把每个字符编码成一个整数。对位移 \(i\) 定义：

\[ X[i]=\sum_{j=0}^{m-1}(t[i+j]-p[j])^2 \]

显然：

\[ X[i]=0 \]

当且仅当所有对应字符都相同，即位移 \(i\) 是一个匹配

展开平方：

\[ \begin{aligned} X[i] &= \sum_{j=0}^{m-1}t[i+j]^2 -2\sum_{j=0}^{m-1}p[j]t[i+j] +\sum_{j=0}^{m-1}p[j]^2 \end{aligned} \]

其中：

• \(\sum t[i+j]^2\) 可以用前缀和在 \(O(1)\) 时间得到每个 \(i\) 的值
• \(\sum p[j]^2\) 是常数
• 难点是交叉项

令：

\[ Y[i]=\sum_{j=0}^{m-1}p[j]t[i+j] \]

只要能快速算出所有 \(Y[i]\)，就能算出所有 \(X[i]\)

用卷积计算交叉项

令 \(t^*\) 是 \(t\) 的反转：

\[ t^*[k]=t[n-1-k] \]

构造两个多项式：

\[ F(x)=\sum_{j=0}^{m-1}p[j]x^j \]

\[ G(x)=\sum_{k=0}^{n-1}t^*[k]x^k \]

看乘积 \(H(x)=F(x)G(x)\) 中 \(x^{n-1-i}\) 的系数：

\[ \begin{aligned} [x^{n-1-i}]H(x) &=\sum_{j=0}^{m-1}p[j]t^*[n-1-i-j]\\ &=\sum_{j=0}^{m-1}p[j]t[i+j]\\ &=Y[i] \end{aligned} \]

因此一次卷积就能得到所有位移的交叉项

算法：

FFT-STRING-MATCHING(t, p)
    encode characters as numbers

    compute prefix sums of t[k]^2
    const_p = sum p[j]^2

    F = polynomial with coefficients p[0], ..., p[m-1]
    G = polynomial with coefficients reverse(t)
    H = F * G using FFT

    for i = 0 to n - m
        cross = coefficient H[n - 1 - i]
        text_part = sum_{k=i}^{i+m-1} t[k]^2
        X = text_part - 2 * cross + const_p
        if X == 0
            report i

总时间为：

\[ O(n\log n) \]

这里默认字符编码满足：两个字符相同当且仅当编码相同

---

带通配符的字符串匹配

若模式串中允许通配符 *，它可以匹配任意字符

可以把通配符位置设为 \(0\)，普通字符编码为非零数

定义新的匹配分数： \[ X[i]=\sum_{j=0}^{m-1}p[j](t[i+j]-p[j])^2 \]

如果 \(p[j]=0\)，这一项自动为 \(0\)，表示通配符不产生约束

如果 \(p[j]\neq 0\)，这一项为 \(0\) 当且仅当：

\[ t[i+j]=p[j] \]

因此：

\[ X[i]=0 \]

当且仅当模式串在位置 \(i\) 匹配文本

展开：

\[ \begin{aligned} X[i] &= \sum_{j=0}^{m-1}p[j]t[i+j]^2 -2\sum_{j=0}^{m-1}p[j]^2t[i+j] +\sum_{j=0}^{m-1}p[j]^3 \end{aligned} \]

这里需要两类交叉相关：

\[ \sum p[j]t[i+j]^2 \]

和：

\[ \sum p[j]^2t[i+j] \]

它们都可以用“模式系数多项式乘以反转文本系数多项式”的方式通过 FFT 求出

具体地：

• 用 \(p[j]\) 和 \(t[k]^2\) 的反转计算第一项
• 用 \(p[j]^2\) 和 \(t[k]\) 的反转计算第二项
• \(\sum p[j]^3\) 是常数

因此带通配符的版本仍然可以在：

\[ O(n\log n) \]

时间内完成

---

迭代 FFT 补充

核心思想是：递归不断按偶数下标和奇数下标拆分，等价于按照下标的二进制位逆序重新排列输入。

例如 \(n=8\) 时，下标的三位二进制和位逆序为：

原下标	二进制	位逆序	新位置
0	000	000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

先做位逆序置换后，再按长度 \(2,4,8,\ldots,n\) 逐层合并。

每个合并单元都由若干个“蝴蝶操作”组成。设当前块长度为 \(m\)，半长为 \(m/2\)，旋转因子为 \(w\)，则一对输入：

\[ u=a[k+j] \]

\[ v=w\cdot a[k+j+m/2] \]

输出为：

\[ a[k+j]=u+v \]

\[ a[k+j+m/2]=u-v \]

这正是递归合并公式：

\[ y_k=y_k^{[0]}+\omega y_k^{[1]} \]

\[ y_{k+n/2}=y_k^{[0]}-\omega y_k^{[1]} \]

迭代实现的优势是：

• 可以原地计算
• 常数较小
• 更容易控制内存
• 工程库通常会进一步优化缓存和旋转因子计算

---

数值精度与整数卷积

标准 FFT 使用复数，因此会有浮点误差

如果输入是整数，理论上卷积结果也是整数。工程实现中常见做法是：

1. 使用双精度或长双精度复数 FFT
2. 逆 FFT 后把接近整数的结果四舍五入
3. 忽略很小的虚部误差

当系数很大或长度很长时，浮点误差可能累积，需要更谨慎的处理。

如果必须精确计算整数卷积，可以使用模意义下的 FFT，也常称为 NTT (Number Theoretic Transform)。它把复数单位根替换成模素数意义下的原根，从而避免浮点误差

只要在某个代数结构中存在合适的主 \(n\) 次单位根，并且 \(n\) 可逆，就可以定义 DFT、逆 DFT 和对应的快速算法

---

小结

本节核心结论：

内容	结论
系数表示	多项式直接用系数向量表示，乘法朴素为 \(O(n^2)\)
点值表示	在相同点上相乘即可得到乘积点值
插值唯一性	\(n\) 个不同点值唯一确定次数界为 \(n\) 的多项式
DFT	在 \(n\) 个单位复数根处求值
FFT	用奇偶拆分和单位根折半性质在 \(O(n\log n)\) 时间计算 DFT
逆 DFT	用 \(\omega_n^{-1}\) 做 FFT 后整体除以 \(n\)
多项式乘法	FFT 求值，逐点相乘，逆 FFT 插值，总时间 \(O(n\log n)\)
卷积	多项式乘法的系数就是卷积
等距 1	用 \(P(x)^2\) 的系数统计两端点之和
字符串匹配	用卷积快速计算所有位移的相关项

从算法设计角度看，FFT 展示了一个技巧：当直接处理对象困难时，可以换一种表示方法；如果两种表示之间能快速转换，就可能让原本昂贵的操作变得便宜