San*_*ndy 11 graph breadth-first-search time-complexity depth-first-search
我知道堆栈溢出中存在类似的问题,其中一个人问过,为什么BFS/DFS的时间复杂度不仅仅是O(V).
给出的适当答案是在完整图的情况下E可以与V ^ 2一样大,因此在时间复杂度中包括E是有效的.
但是,如果V不能大于E + 1.那么,在那种情况下,时间复杂度中没有V,应该有效吗？
axi*_*iom 10
如果它被赋予的是E = kV + c,对于一些真正的常量k和c以后,
O(E + V) = O(kV + c + V) = O(V) = O(E)和你的说法是正确的.
树木就是一个例子.
然而,总的来说,E = O(V^2)我们不能做得更好O(V^2).
为什么不总是只写O(E)？
请注意,可能存在图中根本没有边缘的情况(即O(E) ~ O(1)).即使对于这种情况,我们也要去每个顶点(O(V)),我们无法及时完成O(1).
因此,O(E)一般而言,只写作不会.