戴克斯特拉的算法是线性时间吗？

Question

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

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

Answer 1

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

Answer 2

"如果有对数是线性的"问题的答案是否定的。 线性通常指 O(N(

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