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

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

每个顶点都可以连接到(V-1)个顶点，因此每个顶点的相邻边数为V-1。假设E表示连接到每个顶点的V-1边。

在最小堆中查找和更新每个相邻顶点的权重是O(log(V))+ O(1)或O(log(V))。

因此，从上面的步骤1和步骤2开始，更新顶点的所有相邻顶点的时间复杂度为E *(logV)。或E*logV。

因此，所有V个顶点的时间复杂度为V *(E * logV)，即O(VElogV)。

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

最佳答案

Dijkstra的最短路径算法是O(ElogV)，其中:

V是顶点的数目

E是边的总数

您的分析是正确的，但是符号有不同的含义!您说算法是O(VElogV)，其中:

V是顶点的数目

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

让我们将E重命名为N。因此，一种分析是O(ElogV)，另一种是O(VNlogV)。两者都是正确的，实际上是E = O(VN)。区别在于ElogV是更严格的估计。