计算所有距离的总和

Question

我在一条线上得到了 n 个点及其位置。我需要计算每对点之间的距离之和。是否可以实现复杂度为 O(n) 的操作？

示例：给定三个点，其坐标为 a(-1)、b(-3)、c(3)。所需金额： |-1 + 3| + | - 1 - 3| + |-3 - 3 | = 12

请帮我。

Answer 1

1. 计算每个连续段的长度：

   for (int i=0;i<n-1;i++) len[i]=x[i+1]-x[i];
   

请注意，这是针对排序点的。如果不是，请在计算连续段长度之前进行排序。

2. 计算每个线段在不同的成对距离中出现的次数：对于某些线段，线对的数量为 leftSidePoints*rightSidePoints。换句话说，您计算每个段长度对总长度的贡献。

    for (int i=0;i<n-1;i++) contributionOfSegment[i]=len[i]*(i+1)*(n-i-1);
   

   i+1n-i-1是第 i 段的左侧点，是右侧点

3. 答案是所有部分贡献的总和：

    int sum=0; for (i=0;i<n-1;i++) sum+=contributionOfSegment[i];
   

更新

几乎O(N)algo，nor O(Nlog(N))（标准排序），nor O(maxX)（计算排序）。复杂性O(N)loglog(maxX))或者说更简单，对于 32 位整数O(N)*number_of_bits_in_maxX而言，几乎是线性的。5N

主要逻辑仍然如我上面所描述的那样。瓶颈点是排序——O(N)*number_of_bits_in_maxX因素是排序步骤。我们将使用Van Emde Boas 树对数组进行排序。该树支持 findNext(x) 操作 - 查找 x 之后的下一个元素，复杂度为O(loglogmaxX)。插入也有复杂性O(loglogmaxX)。

所以，Van Emde Boas 排序看起来像：

1. O(N)*number_of_bits_in_maxX在via中填充树for(i=0;i<n;i++) tree.insert(x[i])，其中x未排序的输入数组。
2. O(N)在未排序数组中查找最小值
3. 排序数组[0]=最小值
4. for(int i=1;i<n;i++) sortedArray[i] = tree.findNext(sortedArray[i-1])

然后，使用我上面的逻辑，只需替换数组x：sortedArray

请注意，VEBTree 排序仅在理论上有意义，实际上它可能隐藏了常数因子，并且对于较小的N，log(N)可能比 更好loglog(maxX)，因此，标准排序可能比树排序更快。N如果 VEBTree非常大而maxX只是 32 或 64 位整数，那么它会很酷。