一个O(|E|+|V|)的算法是否被认为是O(|E|)的算法？

Question

当我被要求设计一个O(|E|)的算法时，设计一个O(|E|+|V|)的算法并称之为O(|E|)，是否可行？（如果图是连通的）

答案是可以。因为在连通的情况下，O(|E|+|V|)实际上就是O(|E|)，因为|V|≤|E|+1。

- AspiringMat

Answer 1

简短回答：
O(|E|) 指的是每条边只需要遍历（处理）一定次数（平均），因此，您也需要使用 O(|E|+|V|) 的复杂度来处理顶点。

稍微详细一点的回答：
你需要问自己的问题是：

如果我增加边的数量（对于大量的边），算法是否需要大约两倍的时间才能执行。 如果答案是是，那么您的复杂度为O(|E|)。

最后请记住，在连通图中，最大的|V|数量是|E|+1，因为|E|>=|V|-1。 因此，在最坏情况下，O(|E|+|V|)是O(2|E|+1) = O(|E|)

- Kostas

---

最大的 |V| 值为 |E|+1，而不是 |E|-1。这并不改变其他部分的答案。 - Sebastian Mendez

@Kostas 你为什么撤销了我的编辑？在一个连通图中，|E|>=|V|-1 意味着 |V| <= |E|+1。你编辑的答案是错误的。 - AspiringMat

Answer 2

如果图是连通的，则边的数量（即|E|）至少比顶点数（即|V|-1）少一个。因此，|E|+|V|=O（|E|+|E|+1）=O（|E|）。所以，如果你的算法是O（|E|），那么它也是O（|E|+|V|）。

- trincot