algorithm - 卷积的有效方法，如求和评估

Question

问题给定 N 个 3 维点，它们是 {$p_1,p_2,..,p_n$} 其中 $p_i = (x_i,y_i,z_i) $ 。我必须找到公式的值

对于某些给定的常数整数 P、Q、R、S。所有数字都在 1 和 M 之间（= 100）。

我需要一种有效的方法来计算这个公式

请提供有关如何比 $O(n^2)$ 更好地降低复杂性的任何想法

Answer 1

假设所有坐标都在 1 到 100 之间，那么您可以通过以下方式执行此操作：

1. 计算所有点 O(100*100*100) 操作的 3d 直方图。

2. 使用 FFT 计算直方图沿 3 个轴的卷积

这将产生 3d 矢量的 3d 直方图。然后，您可以遍历此直方图以计算您想要的值。

要点是计算值直方图的卷积计算这些值的成对差异的直方图。这也可以用于以类似方式计算值总和的直方图。

Answer 2

你的问题看起来像一个粒子势问题（例如你在电动力学中遇到的那种），你必须通过对粒子(x_j, y_j)的所有基本贡献求和来在该位置找到一些“势”。i-th

专门针对这类问题的快速算法是快速多极法。查找这个关键字，但我必须警告你，它绝不是简单的理解或实现。需要强大的数学背景。