algorithm - 一维点的成对距离

Question

是否可以比 O(n^2) 更快地计算一维中一组点的成对距离（所有点都在一条线上）？

Answer 1

如果线的给定点在数组中，我们可以在O(N)中创建一个算法来计算成对距离。排序的复杂度为Nlog(N)，因此总体复杂度为Nlog(N)。

将排序后的点的前缀总和存储在数组中，并将点的总和存储在变量 sum 中。

//suppose elements in the array is sorted and psum is prefix sum of array

ans=0, sum=psum[n-1];   //sum is total sum of points

for(i=0;i<n;i++)
   ans+=((sum-psum[i]) - arr[i]*(n-i-1));

// (sum-psum[i]) will give the sum of all the numbers which are greater than arr[i]
// now we need to substract arr[i] (n-i-1) number of times
// all (n*n-n)/2 pairs distance will be calculated

cout<<ans;

Answer 2

在少于 O(N²) 的操作中计算 O(N²) 距离显然是不可能的。

如果您只需要一些按需距离，则在 O(1) 中计算单个距离；不要预先计算所有这些。

如果您的问题实际上是关于最近的点对，那么一维版本是直接的：排序并找到最近的连续点。最远点对更简单：在 O(N) 时间内找到最小值和最大值。或者，也许你正在寻找另一个问题......