FFT

edition_Ant--

2026-07-05 08:56:53

发布于：浙江

4阅读

0回复

0点赞

一、

给定多项式：

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

目标：快速计算：

$A(x_0),A(x_1),\dots,A(x_{n-1})$

暴力复杂度：

$O(n^2)$

FFT 目标：

$O(n\log n)$

二、单位根）

1. n 次单位根定义

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

性质：

$\omega_n^n=1$

2 基本引理

折半引理

$\omega_{2n}^{2k}=\omega_n^k$

消去引理

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

三、多项式拆分

将 A(x) 按奇偶拆分：

$\begin{aligned} A(x)&=a_0+a_1x+\dots+a_{n-1}x^{n-1}\\ &=(a_0+a_2x^2+\dots)+(a_1x+a_3x^3+\dots)\\ &=A_e(x^2)+xA_o(x^2) \end{aligned}$

其中：

$\begin{aligned} A_e(x)&=a_0+a_2x+\dots\\ A_o(x)&=a_1+a_3x+\dots \end{aligned}$

四、DFT 递归

在单位根处求值：

$y_k=A(\omega_n^k)$

代入奇偶分解：

$A(\omega_n^k)=A_e(\omega_n^{2k})+\omega_n^kA_o(\omega_n^{2k})$

由折半引理：

$\omega_n^{2k}=\omega_{n/2}^k$

于是：

$A(\omega_n^k)=A_e(\omega_{n/2}^k)+\omega_n^kA_o(\omega_{n/2}^k)$

同理：

$A(\omega_n^{k+n/2})=A_e(\omega_{n/2}^k)-\omega_n^kA_o(\omega_{n/2}^k)$

一对结果，只用算一半

五、递归 FFT 伪代码

fft(a):
    n=size(a)
    if n==1:return a
    ae=a[0,2,...]
    ao=a[1,3,...]
    ye=fft(ae)
    yo=fft(ao)
    for k=0→n/2-1:
        w=pow(w_n,k)
        y[k]=ye[k]+w*yo[k]
        y[k+n/2]=ye[k]-w*yo[k]
    return y

复杂度：

$T(n)=2T(n/2)+O(n)\Rightarrow O(n\log n)$

六、蝴蝶操作

核心计算单元：

$\begin{cases} u=y_e\\ v=\omega_n^k y_o \end{cases} \Rightarrow \begin{cases} y_k=u+v\\ y_{k+n/2}=u-v \end{cases}$

这就是蝴蝶结构的来源。

七、迭代 FFT

1. 递归的问题

函数调用开销
内存访问不连续

2. 迭代思想

自底向上合并
每一层处理长度为 len 的区间

3. 位逆序置换（Rader）

索引二进制反转后排序：

目的：让递归叶子顺序对齐~

八、迭代 FFT の流程

bitReverse(a)
for len=2→n step*=2:
    wlen=pow(w_n, n/len)
    for i=0→n step+=len:
        w=1
        for k=i→i+len/2:
            u=a[k]
            v=w*a[k+len/2]
            a[k]=u+v
            a[k+len/2]=u-v
            w*=wlen

九、逆 FFT（IFFT）

DFT 矩阵：

$F_{jk}=\omega_n^{jk}$

逆变换：

$F^{-1}=\frac{1}{n}\overline{F}$

实现方法：
把 ω_n 换成 ω_n^{-1}
最后整体除以 n

十、卷积

多项式乘法：

$c=a*b$

步骤：

$\begin{aligned} &\text{FFT}(a)\rightarrow A\\ &\text{FFT}(b)\rightarrow B\\ &C_k=A_kB_k\\ &\text{IFFT}(C)\rightarrow c \end{aligned}$

复杂度：

$O(n\log n)$

十一、边界条件

项目	要求
n	2 的幂
模运算	NTT
精度	double / long double
长度	≥ deg(a)+deg(b)+1

十二、速记公式卡片

$\boxed{ \begin{aligned} &\omega_n=e^{2\pi i/n}\\ &\omega_{2n}^{2k}=\omega_n^k\\ &A(\omega_n^k)=A_e(\omega_{n/2}^k)+\omega_n^kA_o(\omega_{n/2}^k)\\ &\text{蝴蝶}:y_k=u+v,\ y_{k+n/2}=u-v\\ &\text{IFFT}: \omega_n\rightarrow\omega_n^{-1},\ /n \end{aligned} }$