Xecades's Neverland

「离散傅里叶变换」和「离散傅里叶反变换」

离散傅里叶变换（Discrete Fourier Transform, DFT）和离散傅里叶反变换（Inverse Discrete Fourier Transform, IDFT） 是鼎鼎大名的快速傅里叶变换（Fast Fourier Transform, FFT）的前置知识.

其中 FFT 用于加速两个多项式 $A(x)$、$B(x)$ 的乘积 $C(x)$ 的计算，DFT 和 IDFT 是 FFT 的两个中间步骤.