了解 Dijkstra 算法的时间复杂度计算 [英] Understanding Time complexity calculation for Dijkstra Algorithm

问题描述

根据我的理解，我使用下面给出的邻接列表将 Dijkstra 算法的时间复杂度计算为大 O 表示法.它没有像预期的那样出现，这让我一步一步地理解它.

As per my understanding, I have calculated time complexity of Dijkstra Algorithm as big-O notation using adjacency list given below. It didn't come out as it was supposed to and that led me to understand it step by step.

1. 每个顶点都可以连接到 (V-1) 个顶点，因此每个顶点的相邻边的数量是 V - 1.假设 E 表示连接到每个顶点的 V-1 个边.
2. 寻找和更新最小堆中每个相邻顶点的权重为 O(log(V)) + O(1) 或 O(log(V)).
3. 因此从上面的 step1 和 step2，更新一个顶点的所有相邻顶点的时间复杂度是 E*(logV).或 E*logV.
4. 因此所有 V 顶点的时间复杂度为 V * (E*logV)，即 O(VElogV).

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

But the time complexity for Dijkstra Algorithm is O(ElogV). Why?

推荐答案

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

Dijkstra's shortest path algorithm is O(ElogV) where:

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

• V is the number of vertices
• E is the total number of edges

你的分析是对的，但是你的符号有不同的含义！你说算法是 O(VElogV) 其中:

Your analysis is correct, but your symbols have different meanings! You say the algorithm is O(VElogV) where:

• V 是顶点数
• E 是附加到单个节点的最大边数.

• V is the number of vertices
• E is the maximum number of edges attached to a single node.

让我们将您的 E 重命名为 N.所以一个分析说O(ElogV)，另一个分析说O(VNlogV).两者都是正确的，事实上E = O(VN).不同之处在于 ElogV 是一个更严格的估计.

Let's rename your E to N. So one analysis says O(ElogV) and another says O(VNlogV). Both are correct and in fact E = O(VN). The difference is that ElogV is a tighter estimation.

这篇关于了解 Dijkstra 算法的时间复杂度计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！