algorithm - 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)？

标签： algorithmgraphbig-ocomplexity-theory

Answer 1

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

是的。

其中 V 是顶点集，k 是某个顶点具有的邻居数

这个定义是不正确的，因为k依赖于“某个顶点” `所以你需要将它定义为最大度数（一个顶点具有的最大边数）才能有一个可用的定义。

---

关于max-degree，O(maxdeg * |V|)不等于O(|E|)。最大度数是比 更差的复杂度近似值|E|。

想象一下一个图，它有一个顶点，它有1_000边，但其他每个顶点只有1边。

但由于 Big-O 只定义了上限，所以算法当然还在O(maxdeg * |V|).

---

在任何情况下，您最多只能在图中的每条边上查看一次，所以|E|. 边的数量是所有顶点的所有出边的总和，即你试图用|V| * k. 所以两者是完全一样的。IE

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

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

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

通常，将图视为具有顶点和边的实体更为常见，操作依赖于V和E。说起来比从“顶点及其传出边缘”O(|E|)角度来看事情过于复杂要简单得多。