algorithm - 在 Nlg(N) 中计算 res[i+j] = a[i]*b[j]

Question

可能重复：
快速卷积算法

我有两个长度为 N 的数组 a 和 b。我想将结果数组计算为

res[i+j] += a[i]*b[j]

是否可以使用 FFT 或类似的东西在时间上比 N^2 更快地计算出来。我已经看到了这个问题1D Fast Convolution without FFT但我不确定如何使用 FFT 来做到这一点。

EG: A=[1,2,3],B[2,4,6]
res[3] = A[1]*B[2]+A[2]*B[1]

提前致谢

Answer 1

据我了解，您想要 FFT 算法。这里你有这个算法的实现，以及如何实现 FFT 算法的一个很好的解释。