c++ - 在线性时间内使用邻接表创建顶点对

Question

我有 n 个顶点，编号为 1...n，我想将每个顶点与所有其他顶点配对。这将导致 n*(n-1)/2 个边。每个顶点都有一定的强度。两个顶点的强度之差就是边的权重。我需要得到总权重。使用两个循环，我可以在 O(n^2) 时间内完成此操作。但我想减少时间。我可以使用邻接列表并使用它创建一个 n*(n-1)/2 条边的图，但是我将如何在不使用两个循环的情况下创建邻接列表。输入只需要顶点的数量和每个顶点的强度。

for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
    {
        int w=abs((strength[i]-strength[j]));
            sum+=w;
    }

这是我之前所做的。我需要一个更好的方法来做到这一点。

Answer 1

如果有 O(N*N) 条边，则无法在线性时间内列出所有边。

但是，如果您确实需要计算总和，那么这里有一个 O(N*log(N)) 的解决方案。您可以使用 O(N) 排序算法来改进解决方案，例如 radix sort .

#include <algorithm>
#include <cstdint>

// ...

std::sort(strength, strength+n);
uint64_t sum = 0;
int64_t runSum = strength[0];
for(int i=1; i<n; i++) {
  sum += int64_t(i)*strength[i] - runSum;
  runSum += strength[i];
}
// Now "sum" contains the sum of weigths over all edges

算法解释:

这个想法是为了避免显式地对所有边求和(需要 O(N*N))，而是一次添加多个权重的总和。考虑最后一个顶点 n-1 和平均 A[n-1] = (strength[0] + strength[1] + ... + strength[n-2])/(n-1):显然我们可以添加 (strength[n-1] - A[n-1]) * (n-1)，即 n-1 权重，如果权重都大于 strength[n-1]，或者都小于它。但是，由于 abs 操作，我们必须根据其他顶点的强度是大于还是小于当前顶点的强度来添加不同的量。因此，一种解决方案是先对强度进行排序，以确保每个下一个强度都大于或等于前一个。