Part 7.5：快速傅里叶变换 (FFT)——算法世界的蝶之舞

引言：当 O(n²) 成为瓶颈

想象一下，你要计算两个非常大的多项式（或两个大整数）的乘积。一个 n-1 次的多项式有 n 个系数。如果使用我们在中学学过的朴素乘法，将第一个多项式的每一项与第二个多项式的每一项相乘，总共需要进行 n * n = n² 次乘法。当 n 达到百万级别时，O(n²) 的计算量是不可接受的。

这个问题在计算机科学的许多领域都至关重要：

大数乘法：将大整数看作一个以 10 为基的多项式。
信号处理：计算卷积，这是滤波、降噪等操作的核心。
图像处理：二维卷积用于图像模糊、锐化等特效。

有没有一种算法，能突破 O(n²) 的壁垒，实现近乎线性的计算速度？

答案是肯定的，这就是快速傅里叶变换 (Fast Fourier Transform, FFT)。它是一种基于分治思想的革命性算法，能将上述问题的计算复杂度奇迹般地降低到 **O(n log n)**。

为什么 FFT 如此重要？

面试价值：FFT 是算法面试中的“终极 Boss”之一。它综合了分治、递归、复数等多个知识点，能完整地理解并实现 FFT，是候选人算法深度和数学功底的绝佳证明。
学术与工程价值：FFT 是数字信号处理 (DSP) 的基石，是现代通信、音频/视频编解码、雷达、医学成像等无数技术的核心。高德纳（Donald Knuth）称其为“我们这个时代最重要的算法”。

本文将为你揭开 FFT 的神秘面纱，从多项式的两种表示法入手，逐步深入其核心——单位复根和蝶形运算，让你彻底理解这一算法的精妙之处。

背景知识：多项式的两种表示法

要理解 FFT，首先必须知道多项式有两种完全等价的表示方法。

1. 系数表示法 (Coefficient Representation)

这是我们最熟悉的方法。一个 n-1 次的多项式 A(x) 可以表示为：
A(x) = a₀ + a₁x + a₂x² + ... + aₙ₋₁xⁿ⁻¹
这等价于一个系数向量 (a₀, a₁, ..., aₙ₋₁)。

乘法：两个 n-1 次多项式相乘，得到一个 2n-2 次的多项式，时间复杂度为 O(n²)。

2. 点值表示法 (Point-Value Representation)

一个 n-1 次的多项式可以由 n 个不同的点唯一确定。因此，我们可以用 n 个点值对 {(x₀, y₀), (x₁, y₁), ..., (xₙ₋₁, yₙ₋₁)} 来表示它，其中 yᵢ = A(xᵢ)。

乘法：假设 C(x) = A(x) * B(x)。如果我们有 A(x) 和 B(x) 在相同 n 个点 xᵢ 上的点值表示，那么 C(x) 在这些点上的点值就是对应 y 值的乘积！
C(xᵢ) = A(xᵢ) * B(xᵢ)
这个计算只需要 O(n) 的时间！

算法的新思路

这启发了一条全新的计算路径：

求值 (Evaluation)：选择 2n 个点，将系数表示的 A(x) 和 B(x) 转换为点值表示。（这是 FFT 的核心任务）
**逐点相乘 (Pointwise Multiplication)**：用 O(n) 的时间计算出 C(x) 的点值表示。
插值 (Interpolation)：将 C(x) 的点值表示转换回系数表示。（这是逆 FFT (IFFT) 的任务）

如果“求值”和“插值”能足够快，我们就能突破 O(n²) 的瓶颈。FFT 就是那个让这一切成为可能的魔法。

详细算法原理

直觉：聪明的选点

朴素地求值（将 2n 个点分别代入多项式）需要 O(n²) 的时间。FFT 的天才之处在于，它不选择任意的点，而是选择一组具有高度对称性的特殊点——**单位复根 (Complex Roots of Unity)**。

这些点的对称性使得大量的计算可以被重复利用，从而将问题规模不断减半，完美契合分治思想。

严谨原理：单位复根与蝶形运算

1. 单位复根

n 次单位复根是指方程 zⁿ = 1 在复数范围内的 n 个解。它们可以表示为：
ωₙᵏ = e^(2πik/n) = cos(2πk/n) + i * sin(2πk/n)，其中 k = 0, 1, ..., n-1。

单位复根有两条至关重要的性质：

**折半引理 (Halving Lemma)**：(ω₂ₙ²ᵏ) = ωₙᵏ。这使得 2n 次单位复根的偶数项可以与 n 次单位复根对应。
**消去引理 (Cancellation Lemma)**：ωₙ^(k+n/2) = -ωₙᵏ。这揭示了单位复根的对称性，n/2 之后的根可以通过 n/2 之前的根取反得到。

2. FFT 的分治策略

FFT 的核心是将一个 n 项的多项式 A(x) 按系数的奇偶性分解为两个 n/2 项的多项式：

A_even(x) = a₀ + a₂x + a₄x² + ...
A_odd(x) = a₁ + a₃x + a₅x² + ...

原多项式可以重写为：A(x) = A_even(x²) + x * A_odd(x²)

现在，我们将 n 次单位复根 ωₙᵏ (k = 0, ..., n/2 - 1) 代入：

A(ωₙᵏ) = A_even((ωₙᵏ)²) + ωₙᵏ * A_odd((ωₙᵏ)²)
= A_even(ω_(n/2)ᵏ) + ωₙᵏ * A_odd(ω_(n/2)ᵏ) (利用折半引理)

再代入对称点 ωₙ^(k+n/2)：

A(ωₙ^(k+n/2)) = A_even(ω_(n/2)ᵏ) - ωₙᵏ * A_odd(ω_(n/2)ᵏ) (利用消去引理)

**蝶形运算 (Butterfly Operation)**：
我们发现，计算 A(ωₙᵏ) 和 A(ωₙ^(k+n/2)) 需要的 A_even(ω_(n/2)ᵏ) 和 A_odd(ω_(n/2)ᵏ) 是完全相同的！我们只需要递归地计算出这两个子问题的值，然后通过一次加法和一次减法，就能得到两个点的求值结果。这种计算结构在图示中形如蝴蝶，因此得名。

关键图示

图示标题：8点FFT的蝶形运算图
图示描述：
一个三层网络图。输入在最左边，是经过“位倒序”排列的原始系数。输出在最右边。
第一层：每 2 个点为一组进行蝶形运算。
第二层：每 4 个点为一组进行蝶形运算。
第三层：所有 8 个点进行一次大的蝶形运算。
图中充满了交叉的线，每个交叉点就是一个蝶形运算，它接收两个输入，产生两个输出。

步骤分解

**位倒序 (Bit-reversal)**：为了让递归的实现更高效（可以迭代实现），需要先对输入的系数向量进行位倒序排列。
迭代计算：从底层开始，逐层向上进行蝶形运算。
- 第一层，步长为 2，计算 2 点 FFT。
- 第二层，步长为 4，计算 4 点 FFT。
- …直到完成 n 点 FFT。
**逆 FFT (IFFT)**：插值过程与 FFT 惊人地相似。只需将 FFT 中的单位复根 ωₙ 换成其共轭 ωₙ⁻¹，然后对结果的每一项再除以 n 即可。

Python 实现

import cmath

def fft(a):
    """递归实现的快速傅里叶变换"""
    n = len(a)
    if n == 1:
        return a

    # 分解为奇数项和偶数项
    a_even = a[0::2]
    a_odd = a[1::2]

    # 递归解决子问题
    y_even = fft(a_even)
    y_odd = fft(a_odd)

    # 合并
    y = [0] * n
    omega_n = cmath.exp(2j * cmath.pi / n)
    omega = 1
    for k in range(n // 2):
        t = omega * y_odd[k]
        y[k] = y_even[k] + t
        y[k + n // 2] = y_even[k] - t
        omega *= omega_n
    return y

def ifft(y):
    """快速傅里叶逆变换"""
    n = len(y)
    # IFFT 等价于对共轭复数做 FFT，再取共轭，最后除以 n
    a_conj = [v.conjugate() for v in y]
    y_conj = fft(a_conj)
    return [v.conjugate() / n for v in y_conj]

def polynomial_multiply(p1, p2):
    """使用 FFT 进行多项式乘法"""
    # 确定 FFT 的长度，必须是 2 的幂，且大于等于结果多项式的阶数
    n = 1
    while n < len(p1) + len(p2):
        n *= 2

    # 补零
    p1.extend([0] * (n - len(p1)))
    p2.extend([0] * (n - len(p2)))

    # 1. 求值 (FFT)
    y1 = fft(p1)
    y2 = fft(p2)

    # 2. 逐点相乘
    y_result = [y1[i] * y2[i] for i in range(n)]

    # 3. 插值 (IFFT)
    result_coeffs = ifft(y_result)

    # 转换为整数
    return [round(c.real) for c in result_coeffs]

# --- 案例测试 ---
# A(x) = 1 + 2x + 3x²  => p1 = [1, 2, 3]
# B(x) = 4 + 5x        => p2 = [4, 5]
# C(x) = A(x) * B(x) = 4 + 13x + 22x² + 15x³
p1 = [1, 2, 3]
p2 = [4, 5]

result = polynomial_multiply(p1, p2)
print(f"多项式乘法结果的系数: {result}")

# 期望输出接近 [4, 13, 22, 15, 0, 0, 0, 0]

复杂度推导过程

时间复杂度：O(n log n)

FFT 的时间复杂度分析是分治算法的经典案例。

递归关系式：T(n) = 2 * T(n/2) + O(n)
- 2 * T(n/2)：两次对规模为 n/2 的子问题的递归调用（fft(a_even) 和 fft(a_odd)）。
- O(n)：合并步骤中的 for 循环执行 n/2 次，每次都是常数时间操作。
主定理求解：
- a=2, b=2, d=1。
- log_b(a) = log₂(2) = 1。
- 因为 d = log_b(a)，符合主定理的第二种情况。
- 因此，T(n) = O(n^d * log n) = O(n log n)。

多项式乘法的总时间复杂度 = FFT(A) + FFT(B) + PointwiseMul + IFFT(C)
= O(n log n) + O(n log n) + O(n) + O(n log n) = O(n log n)。

空间复杂度：O(n)

递归实现：递归栈的深度为 O(log n)。但在每一层递归中，我们都创建了新的奇偶数组，总空间为 n + n/2 + n/4 + ... = 2n。因此空间复杂度为 O(n)。
迭代实现：通过位倒序的原地算法，可以将空间复杂度优化到 O(1)（如果不考虑输入输出数组）。

总结

快速傅里叶变换 (FFT) 是算法设计史上的一座丰碑。它通过巧妙地利用单位复根的对称性，将分治思想发挥到极致，成功地将卷积和多项式乘法等问题的复杂度从 O(n²) 降低到了 O(n log n)，为数字时代无数的技术应用奠定了理论基础。

本文核心要点

✅ 核心思想：将系数表示的多项式乘法，通过变换到点值表示，转化为线性时间的运算，再变换回来。
✅ FFT 的作用：高效地完成“求值”这一步（系数 -> 点值）。
✅ IFFT 的作用：高效地完成“插值”这一步（点值 -> 系数）。
✅ 关键技巧：选择单位复根作为求值点，利用其对称性进行蝶形运算，完美契合分治思想。
✅ 复杂度：O(n log n)，是算法优化的典范。

至此，我们已经完成了“Part 7：高级算法”专题的学习。从贪心、分治到随机化和数论，这些算法思想将为你解决更复杂、更抽象的问题提供强大的理论武器。在最后的“Part 8”中，我们将把目光投向工程实践和面试，探讨如何将这些理论知识应用到真实世界中。

大学算法全体系 > Part 7：高级算法

#算法进阶 #分治算法 #FFT #快速傅里叶变换 #多项式 #信号处理

Part 7.5：快速傅里叶变换 (FFT)——算法世界的蝶之舞

https://hjjjkh.github.io/posts/ba38e901

作者

李国强

发布于

2025年11月19日

许可协议

Part 6.7：AC 自动机——多模式匹配的终极武器上一篇

Part 6.6：Trie (字典树)——高效的前缀查询神器下一篇