一尘不染

了解Dijkstra算法的时间复杂度计算

algorithm

根据我的理解,我已使用下面给出的邻接表将Dijkstra算法的时间复杂度计算为big-O表示法。它没有按预期的方式出现,这使我逐步了解了它。

  1. 每个顶点可以连接到(V-1)个顶点,因此每个顶点的相邻边数为V-1。假设E表示连接到每个顶点的V-1边。
  2. 在最小堆中查找和更新每个相邻顶点的权重为O(log(V))+ O(1)或O(log(V))
  3. 因此,从上面的步骤1和步骤2开始,更新顶点的所有相邻顶点的时间复杂度为E *(logV)。或E*logV
  4. 因此,所有V个顶点的时间复杂度为V *(E * logV)即O(VElogV)

但是Dijkstra算法的时间复杂度为O(ElogV)。为什么?


阅读 705

收藏
2020-07-28

共1个答案

一尘不染

Dijkstra的最短路径算法是O(ElogV)

  • V 是顶点数
  • E 是边的总数

您的分析是正确的,但是符号有不同的含义!您说算法在O(VElogV)哪里:

  • V 是顶点数
  • E 是连接到单个节点的最大边数。

让我们将您重命名EN。因此,一种分析说O(ElogV),另一种说O(VNlogV)。两者都是正确的,事实上E = O(VN)。区别在于,这ElogV是一个更严格的估计。

2020-07-28