众所周知，它们的计算复杂度分别为和。$\mathcal{O}(N^2)$$\mathcal{O}(N \log N)$

$\mathcal{O}$表示法忽略了任何确定这些函数运行速度的常量。根据前面的常数，直接计算卷积（或相关）可能会更快。

例如，卷积的傅里叶变换方法可能需要秒，而直接方法可能需要秒。如果，直接法更快。$10^5 N \log N$$10^{-3} N^2$$N = 100$

一般来说，对于较大，傅里叶方法往往更快，加速比增加。有关计算哪种方法更快的更多详细信息，请参阅scipy PR #5608。$N$

下图是将卷积的傅里叶变换方法乘以 ，fftconvolve直接方法乘以convolve。我们看到，对于许多实际大小的数组，直接方法更快。

注意：此图是在卷积 1D 信号时。对于更高维度的信号（2D、3D 等）fftconvolve往往更快

为了给这些图表计时，我使用scipy.signal.fftconvolve了np.convolve默认参数。从 scipy 0.19 版开始，scipy.signal.convolve将在直接和傅立叶变换方法之间进行选择，以选择更快的方法。

也许您刚刚在问题中省略了提及这一点，但一个根本区别是您只能计算傅里叶域中的循环相关/卷积。当然，这可以通过对时间信号进行零填充来克服，但这是一个根本性的区别，可能会影响你决定走哪条路。

我可以想象以下基于卷积的计算可能是首选的情况：

1-您只需要评估几个滞后的相关性。如果滞后数大致小于，则卷积方法实际上更快。例如，在尝试跟踪信号与其延迟版本之间的时间延迟时，您可能会遇到这种情况。在跟踪期间，时间延迟可能会发生一些变化。因此，您很清楚最大相关性发生在哪里，并且您仅在该滞后附近计算相关性。$M$$\log(N)$

2-如果您在 FPGA 等可配置硬件中有整数实现。在这种情况下： - 实施 FFT 需要大量资源。- 要表示 FFT 的输出，您可能需要比原始信号更多的位。在这种情况下，FFT 之后的乘法可能会占用更多资源。极端情况是两个二进制序列之间的相关性。