快速傅里叶变换

快速傅里叶变换，FFT, 是一种通过将计算分解为更小、更易处理的部分来计算离散傅里叶变换的计算算法。

计算一个 N 点 DFT 需要 N² 次复数乘法，而 FFT 算法仅需要 (N/2) log₂N 次乘法，因此具有显著更快的运算性能。

随着 N 的增加，快速傅里叶变换（FFT）通过将运算量从二次方量级降低至对数量级，变得更快且更高效。

它利用对称性和周期性特性，最大限度地减少冗余计算和乘法运算。

逆快速傅里叶变换，IFFT, 从频域表示中以更高的计算效率重建原始信号。

信号与图像处理中常用的技术，在无线通信、科学研究和数据分析中也发挥着至关重要的作用。