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. 计算所有点的 3d 直方图 O(100*100*100) 操作。

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

这将产生 3d 向量的 3d 直方图。然后您可以遍历此直方图以计算所需的值。

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