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

Question

可能重复： 快速卷积算法

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

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

是否可以用快速傅立叶变换或类似的时间比N^2更快地计算。我已经看到了这个问题，不需要FFT的一维快速卷积，但不知道如何用FFT来实现。

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

提前感谢

Answer 1

据我所知你想要FFT算法。这里你有一个实现这个算法，也很好地解释了如何实现的快速傅立叶变换算法。