O(|V| * k) 是否等于 O(|E|)？

Question

我假设在表示邻接表时，我们需要遍历所有顶点及其邻居，因此构建邻接表的时间复杂度为 O(|V| * k)，其中 V 是顶点集k 是某个顶点的邻居数（如果图是完整的，则 k = |V| - 1）。但是，我遇到的每个资源都指出构建邻接表的时间复杂度是 O(|E|)，其中 E 是边集。

由于我们考虑的是最坏情况，图的最坏情况是连通图，其中|E|等于 (|V| 2) = (|V| * (|V|-1))/2。如上所述，从完整图构建邻接表需要遍历所有顶点及其邻居。此操作的时间复杂度将为 |V| * k 其中 k 是 |V|-1。所以，它应该是 O(|V| * (|V|-1)) => O(|V|^2)。 由于我们发现边的数量是(V * (V-1)) / 2 => O(|V|^2)，那么两个复杂度，O(|V| * k)和O(|E| ) 应该是一样的。

让我感到困惑的是为什么人们更喜欢使用 O(|E|) 而不是 O(|V| * k)？

Answer 1

Is O(|V| * k) equal to O(|E|)?

是的。

where V is the set of vertices and k is the number of neighbors a certain vertex has

此定义不正确，因为 k 取决于 “特定顶点”`，因此您需要将其定义为最大度数（最大边数一个顶点有）为了有一个可用的定义。

---

注意 max-degree，O(maxdeg * |V|) 不等于 O(|E|)。最大度是比 |E|.

更差的复杂度近似值

试想一个图只有一个顶点有 1_000 条边，但其他所有顶点只有 1 条边。

但是Big-O只定义了上界，算法当然还在O(maxdeg * |V|).

---

在任何情况下，您将最多查看图中的每条边一次，因此 |E|。边的数量是所有顶点的所有出边的总和，即你试图用 |V| * k 制定的内容。所以两者完全相同。即

|E| = sum (v * outdegree(v))

(k 在这种情况下不是最大度数，而是每个 v 特定的出度数)

The thing that confuses me is why people prefer to use O(|E|) instead of O(|V| * k)?

一般来说，更常见的是将图视为具有顶点和边的实体，操作依赖于 V 和 E。只说 O(|E|) 比通过从 “顶点及其出边”-angle.

来观察它使事情变得过于复杂要简单得多。