视频字幕
快速傅里叶变换，简称FFT，是数字信号处理中最重要的算法之一。它能够高效地将时域信号转换为频域表示，揭示信号中包含的各种频率成分。相比直接计算DFT的O(N²)复杂度，FFT将计算复杂度降低到O(N log N)，这使得处理大量数据成为可能。
离散傅里叶变换的定义公式看起来简洁，但直接计算的复杂度是O(N²)。这意味着当数据量增大时，计算时间会急剧增长。例如，处理1024个数据点时，DFT需要约100万次运算，而FFT只需要约1万次运算，效率提升了100倍。
FFT的核心是分治策略。首先将N点DFT分解为两个N/2点的子问题：一个处理偶数下标的数据，另一个处理奇数下标的数据。然后递归地解决这两个子问题。最后，利用单位根的特殊性质，将两个子问题的结果高效地合并成原问题的解。这种分治方法将复杂度从O(N²)降低到O(N log N)。
蝶形运算是FFT算法的核心计算单元，因其计算流图形似蝴蝶翅膀而得名。它接收两个输入a和b，通过单位根W进行加权运算，产生两个输出c和d。具体计算为：c等于a加上W乘以b，d等于a减去W乘以b。这种运算巧妙地利用了复数单位根的周期性和对称性，是FFT高效性的关键所在。
FFT作为数字信号处理的基石，在现代科技的各个领域都有广泛应用。在信号处理中，FFT用于频谱分析和数字滤波；在图像处理中，JPEG压缩和图像增强都离不开FFT；在通信系统中，OFDM调制技术大量使用FFT；在科学计算中，FFT帮助快速求解偏微分方程。可以说，FFT的发明极大地推动了数字时代的发展。