2 
O(|E| + |V| log |V|)

我知道愚蠢的问题，但是如果有日志，它是线性的吗？

4

2 回答 2

7

不，O(VlogV) =/= O(V) 因为 VlogV 与 V 的比率发散到无穷大

于 2012-09-16T01:21:55.740 回答
4

“如果有日志是线性的”这个问题的答案是否定的。线性通常指 O(N)

这意味着它取决于图，并且可以通过同时考虑边和顶点来更精确地测量复杂性。更简单的界限是O(V^2)因为在最坏的情况下|E|=O(V^2)因此O(|V^2| + |V| log |V|) = O(V^2)。在最好的情况下|E| = 0，所以O(|V| log |V|)，所以运行时间从来不是真正的线性。

于 2012-09-16T01:24:18.203 回答