-3

不应该是 E*(logV) 吗?参考:Dijkstra 算法

4

2 回答 2

4

Dijkstra 算法的最坏情况时间复杂度取决于它的实现方式:

简单实现O((E * c1) + (V * V)) = O(E + V^2) ~ O(V^2)

使用斐波那契堆O((E * c2) + (V * log V)) = O(E + V log V) ~ O(V log V)

于 2013-06-04T04:56:12.093 回答
1

在最坏的情况下E > V,复杂性E + VlogV可以替换E+ElogV为复杂性ElogV,这就是您的意思吗?

于 2013-06-04T03:15:15.617 回答