O(|E|+|V|) 算法是否被视为 O(|E|)？

Question

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

Answer 1

简短回答：
O(|E|)指的是每条边只能被遍历（处理）固定次数（平均），所以是的，您还应该处理具有O(|E|+|V|)复杂性的顶点。

更长一点的答案：
您需要问自己的问题是：

如果我将边数加倍（对于大边数），算法的执行时间是否会增加大约两倍。如果答案是肯定的，那么你的复杂性就是O(|E|)。

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