gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:22:05 27 4
gpt4 key购买 nike

<分区>

Possible Duplicate:
Fast convolution algorithm

我有两个长度为 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]

提前致谢

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com