快速傅里叶变换（FFT）超详解

Question

如题所述

Answer 1

快速傅里叶变换（FFT），作为一种高效计算离散傅里叶变换（DFT）的算法，由库利和图基在1965年提出，其核心在于以惊人的[公式] 时间复杂度计算多项式乘积。相比于常规方法的[公式] ，FFT展现出了显著的优势。

多项式乘积通过系数表示，即每个项的系数顺序排列，如[公式]。[公式] 次多项式在给定[公式] 个点值时，可以唯一确定多项式。这意味着，只需将[公式] 点值代入[公式]，我们就能找到对应的[公式] 次多项式。这一过程的关键在于，FFT允许我们在较低的时间复杂度下进行系数到点值的转换，反之亦然，从而加速多项式乘法的计算。

在FFT中，单位根在单位圆上形成[公式] 个复数点，其中[公式] 是最小的正幅角单位根。它们具有特殊性质，如[公式]。通过对多项式[公式] 分解奇偶项，FFT逐步求解，最终将系数表示法转换为点值表示，仅需[公式] 时间复杂度。

逆变换，即离散傅里叶逆变换（IDFT），将点值表示还原为系数表示。这个过程可以用矩阵表示，如[公式]，其中[公式] 是单位根的逆矩阵，使得通过特定运算，可以得到原多项式的系数。

FFT的递归实现，通过单位根的共轭复数操作和分治策略，使得计算更为优化。在此基础上，快速数论变换（NTT）作为FFT的变种，提供了一种精度损失小、速度更快的乘法方法，尤其在特定应用场景中更显优势。