algorithm - 在c ++中找到所有对欧几里得距离的更快方法

Question

说，在 D 维欧几里得空间中，给定 N 个格点，（例如：最高 6D 空间是可能的），现在你必须找到所有对欧几里得距离。现在我们一般用 n^2 循环，但是如果 N = 5000，那么这个 O(n^2) 太慢了，那么有什么有效的方法来找到距离吗？

Answer 1

有 N*(N-1)/2 对，所以 O(N^2) 是可能的最佳时间

Answer 2

虽然@MBo 是正确的，因为这O(N^2)是最好的大 O 时间，但如果这些点确实位于一种特殊的格子上，即矩形格子上，您可以利用对称性来降低前置因子。一般来说，我们可以假设我们有一个 D 维方格，m在每个方向上最多向外延伸。这给出了N=2*d*m分数。我们只需要计算这个格子中的上象限，因为其他维度将是相同的。例如，在 2D 中考虑以下点：

(3,4)   -> 5
(-3,4)  -> 5 
(3,-4)  -> 5 
(-3,-4) -> 5 

通常，您可以将计算量减少一个因子(2^d-1)点，这对于更高的维度非常重要。在 6 维中，这是一个常数因子63。