基于FFT的卷积复杂度为何优于朴素卷积？

嘿，这个问题问到点子上了——很多人刚接触FFT卷积时都会有这样的困惑，我来给你掰扯清楚：

一、为什么M≤log(N)时，FFT卷积仍被认为更优？ #

其实这里要区分「理论渐近复杂度的定义」和「实际工程场景的选择逻辑」：

• 渐近复杂度的核心是N趋向无穷大的表现：我们常说FFT卷积更优，本质是针对M和N同量级的场景（比如两个长信号做卷积），这时候O(N logN)对比O(N²)的优势是碾压级的。而当M是固定小常数时，理论上朴素卷积的O(NM)=O(N)确实比O(N logN)的渐近复杂度更低，但这时候的“优劣势”不能只看复杂度公式：
  • 举个例子：当N=1e6，log₂(N)≈20，如果M=10，朴素卷积是1e7次操作，FFT卷积是2e7次操作，但现代FFT库（比如FFTW）经过SIMD、缓存优化后，单次操作的实际耗时远低于朴素循环的耗时，实际跑起来两者速度可能不相上下，甚至FFT更快。
• 扩展性和维护成本：如果之后你的滤波器长度M需要调整（比如从10变成1000），或者要批量处理上百个信号，FFT卷积的架构不需要大改，预先计算一次滤波器的FFT就能复用；而朴素卷积的耗时会直接随M线性飙升，代码也需要重新优化。这种扩展性上的优势，在工程中往往比单次的理论复杂度更重要。
• 边界处理的便利性：朴素卷积处理线性卷积的边界补零、边缘效应时，需要额外写逻辑；而FFT卷积结合重叠相加/重叠保存法，可以很优雅地处理长信号的分段卷积，代码复杂度更低，不容易出错。

二、当M固定不随N缩放时，实际复杂度更接近什么？ #

当M是固定常数（比如滤波器长度固定，不随待处理信号长度N变化），FFT卷积的理论复杂度还是O(N logN)，但因为logN是对数级增长，它的增长速度其实非常慢：

• 比如N从1e3涨到1e6，log₂(N)只从10涨到20，仅增长了2倍；而朴素卷积的O(NM)会直接增长1000倍。当N足够大时，两者的实际耗时差距会越来越小，甚至FFT因为优化优势反超。
• 如果用重叠相加/重叠保存法优化长信号+短滤波器的卷积，把长信号分成和M相当的块来处理，此时FFT卷积的实际复杂度会接近O(N logM)——因为logM是固定常数，所以本质上也是O(N)，和朴素卷积的理论复杂度一致，但实际运行效率更高。

内容的提问来源于stack exchange，提问作者Oded Sayar