求最接近给定数字的数组中三个元素之和的渐近最优方法
在他对 的回答中这个问题，约翰·费米内拉 (John Feminella) 说：
如果你真的很喜欢，可以通过次二次方来完成这个任务 将每个整数表示为位向量并执行快速 傅立叶变换，但这超出了本答案的范围。
解决该问题中描述的问题的渐近最优方法是什么？
In his answer to this question, John Feminella says:
It's possible to do this sub-quadratically if you get really fancy, by
representing each integer as a bit vector and performing a fast
Fourier transform, but that's beyond the scope of this answer.
What is the asymptotically optimal way of solving the problem described in that question?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
假设我们有一个数组
1 2 4。我们将此数组表示为多项式f(x) = x^1 + x^2 + x^4。我们看一下f(x)^2，它是n的写法，数组的两个元素之和就是x的系数^n，这通常是正确的。 FFT 为我们提供了一种高效乘多项式的方法*，因此基本上我们所做的就是计算f(x)^3并查看目标数 S 的系数。Suppose we have an array
1 2 4. We represent this array as a polynomialf(x) = x^1 + x^2 + x^4. Let's look atf(x)^2, which isThe number of ways to write
nas the sum of two elements of the array is the coefficient ofx^n, and this is true in general. FFT gives us a way to multiply polynomials efficiently*, so basically what we do is computef(x)^3and look at the coefficient of the target number S.