和具有相似长度时，快速卷积比线性卷积更快。假设和的长度分别为和，FFT 的数量应该大于。$x[n]$$y[n]$$x[n]$$y[n]$$M$$L$$N=M+L-1$

快速卷积的复杂度为，而线性卷积的复杂度为。当时，我们有并且快速卷积在中。$O(N\log_2 N)$$O(ML)$$M\gg L$$N\approx M$$O(M\log_2 M)$

时，快速卷积不再快速。因此，我们需要将很长的信号分成块并应用 OLA 或 OLS。$\log_2 M>L$

使用重叠保存或重叠添加的主要原因是延迟。通常您不想在计算第一个输出样本之前等待完整的信号。当然，如果您不需要在处理之前存储完整的信号，您也可以节省内存。

因此，如果您想在频域中进行（准）实时滤波，则需要处理相对较小的信号块。这种类型的处理称为块卷积。Overlap-add和overlap-save是块卷积的两种具体实现。

除了马特的好答案：不要忘记，通常情况下，您的滤波器的脉冲响应将比您要过滤的信号短几个数量级；在这方面，您的公式至少具有误导性（但它遵循 -notation 的基本思想）。$\mathcal O$

你在教科书中读到的时间复杂度本质上是一种理论陈述，与计算现实有些脱节；对于相关大小，您会发现大多数计算架构（在 CPU 和数字逻辑设计世界中）具有高延迟、高带宽、大尺寸外部动态 RAM，然后是缓存层以使其对本地跳转有用操作。如果您的整个计算都适合缓存，那将大大提高速度。我做的最后一个基准测试，期望在现代 x86_64 CPU 上从 RAM 中提取一次需要大约 400 次复数乘法（！）的时间。

因此，认为您的 FFT 在复杂性上“平滑”缩放，如所暗示的，这确实是一种误导。当您的 CPU、其缓存和内存控制器无法为 CPU 准备数据以在本地获取数据时，现实世界的复杂性就会发生跳跃。由于现代计算优化 CPU 中通常有三层缓存，因此您会非常显眼地看到这些缓存。一旦您的大小通常超出任何缓存大小，然后仍然值得意识到这是一个增长率限制，而不是实际的上限，所以想象一下前面的任意常数。$N\log N$$N \log N$