根据我的理解,我已使用下面给出的邻接表将Dijkstra算法的时间复杂度计算为big-O表示法。它没有按预期的方式出现,这使我逐步了解了它。
O(log(V))
E*logV
O(VElogV)
但是Dijkstra算法的时间复杂度为O(ElogV)。为什么?
Dijkstra的最短路径算法是O(ElogV):
O(ElogV)
V
E
您的分析是正确的,但是符号有不同的含义!您说算法在O(VElogV)哪里:
让我们将您重命名E为N。因此,一种分析说O(ElogV),另一种说O(VNlogV)。两者都是正确的,事实上E = O(VN)。区别在于,这ElogV是一个更严格的估计。
N
O(VNlogV)
E = O(VN)
ElogV