问题 给定 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)$ 更好地降低复杂性的想法
最佳答案
假设所有坐标都在 1 到 100 之间,那么您可以通过:
计算所有点的 3d 直方图 O(100*100*100) 操作。
使用 FFT 沿 3 个轴中的每一个计算直方图的卷积
这将产生 3d 向量的 3d 直方图。然后您可以遍历此直方图以计算所需的值。
要点是,计算值直方图的卷积会计算这些值的成对差异的直方图。这也可以用于以类似的方式计算值总和的直方图。
关于algorithm - 卷积的有效方法,如求和评估,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32542049/