快速傅里叶变换 背景：从多项式乘法到卷积 考虑两个多项式：A(x) = a₀ + a₁x + a₂x² + ... 和 B(x) = b₀ + b₁x + b₂x² + ... 它们的乘积 C(x) = A(x) * B(x) 的系数 cₖ 由 aᵢ 和 bⱼ 的卷积求和得到：cₖ = Σ (aᵢ * bₖ₋ᵢ)。直接计算所有系数 cₖ 的时间复杂度是 O(n²)。这个计算瓶颈在许多信号处理、图像分析等领域普遍存在，其核心数学运算就是卷积。快速傅里叶变换的核心价值在于它能将计算卷积的复杂度从 O(n²) 降低到 O(n log n)。 关键思想：改变多项式的表示法 直接使用系数列表 [a₀, a₁, ..., aₙ₋₁] 来表示多项式，称为 系数表示法 。这种表示法下，多项式乘法（卷积）的计算成本很高。FFT 采用了一个更聪明的策略： 点值表示法 。 一个 n-1 次多项式可以由其在 n 个不同点上的取值唯一确定。因此，我们可以用 {(x₀, A(x₀)), (x₁, A(x₁)), ..., (xₙ₋₁, A(xₙ₋₁))} 这 n 个点值对来表示同一个多项式。 点值表示法的优势 在点值表示法下，多项式乘法变得异常简单。假设我们有相同一组点 x₀, x₁, ..., x₂ₙ 上 A(x) 和 B(x) 的点值，那么乘积 C(x) 在同一个点 xₖ 上的值就是 C(xₖ) = A(xₖ) * B(xₖ) 。因此，点值表示法的乘法时间复杂度是线性的 O(n)。整个计算流程变为： 系数表示 → 点值表示 → (点乘) → 点值表示 → 系数表示 。 其中，在点值表示下的乘法是高效的，但关键挑战在于如何在两种表示法之间高效转换。 转换的挑战与DFT 如何在系数表示和点值表示之间转换？如果随意选择点 xₖ ，从系数求值（正变换）需要 O(n) per point，总共 O(n²)；从点值插值回系数（逆变换）解一个线性方程组，也需要 O(n³)。这没有带来任何好处。 离散傅里叶变换定义了一种特殊的点值选取：取 xₖ 为 单位根 ，即方程 xⁿ = 1 的 n 个复数根。具体地，我们定义主 n 次单位根为 ωₙ = e^(2πi/n) ，那么 n 个单位根就是 ωₙ⁰, ωₙ¹, ..., ωₙⁿ⁻¹ 。在单位根处求值，就是计算 DFT： Ýⱼ = Σₖ₌₀ⁿ⁻¹ yₖ * ωₙ^(-j k) 。 FFT的巧妙之处：分而治之 FFT 是计算 DFT 的一种快速算法，其核心是 分治策略 ，利用单位根的对称性和周期性性质。 考虑一个 n 项多项式（设 n 是 2 的幂），我们可以按指数奇偶性将其拆分为两个规模减半的子问题： A(x) = Aₑ(x²) + x * Aₒ(x²) 其中 Aₑ 包含所有偶数项系数， Aₒ 包含所有奇数项系数。 现在，关键点来了：当我们将 n 个单位根 ωₙʲ (j=0,1,...,n-1) 代入时，我们发现 (ωₙʲ)² 的值并不是 n 个不同的数，而是 n/2 个单位根 ωₙ/₂ʲ 的两次重复。这个 折半 性质意味着，要计算规模为 n 的 DFT，我们只需要计算两个规模为 n/2 的 DFT（分别对偶数列和奇数列），然后再用 O(n) 的时间组合结果。这将一个 O(n²) 的问题变成了 O(n log n)。 算法流程与逆变换 FFT 算法（以最经典的 Cooley-Tukey 算法为例）递归地应用上述分治思想，其时间复杂度为 O(n log n)。 逆变换，即从点值表示（在单位根处采样）恢复系数表示，其数学形式与正向变换极其相似，只是将单位根 ωₙ 替换为其共轭复数 ωₙ⁻¹ ，并在最后将结果除以 n。因此，逆变换同样可以用一个 O(n log n) 的快速算法（IFFT）来完成。 应用与影响 FFT 是计算科学史上最重要的算法之一。它的应用极其广泛，远超多项式乘法，包括： 信号处理 ：音频/图像/视频的滤波、频谱分析。 数据压缩 ：JPEG, MP3 等格式的核心。 求解偏微分方程 ：特别是谱方法。 大整数乘法 ：将大数视为以基数为变量的多项式。 FFT 将卷积操作的复杂度从 O(n²) 降至 O(n log n)，这带来了计算效率的质的飞跃，使得许多以前不可行的实时计算和大规模模拟成为可能。