了解Dijkstra算法的时间复杂度计算
根据我的理解，我已使用下面给出的邻接表将Dijkstra时间复杂度" title="算法的时间复杂度">算法的时间复杂度计算为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是一个更严格的估计。
以上是 了解Dijkstra算法的时间复杂度计算 的全部内容， 来源链接： utcz.com/qa/419261.html
