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

Question

根据我的理解,我使用下面给出的邻接表将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).为什么？

Answer 1

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

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

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

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

让我们重命名你E来N.一个分析说O(ElogV),另一个分析说O(VNlogV).两者都是正确的,事实上E = O(VN).不同的是,这ElogV是一个更严格的估计.

Answer 2

添加更详细的解释，以防万一：

• O(对于使用最小堆的每个顶点：对于每个边线性：将顶点推到该边指向的最小堆)
• V = 顶点数
• O(V * (从最小堆弹出顶点+在边缘中找到未访问的顶点*将它们推到最小堆))
• E = 每个顶点上的边数
• O(V * (从最小堆弹出顶点+ E *将未访问的顶点推送到最小堆))。请注意，在我们“访问”它之前，我们可以在此处多次推送同一个节点。
• O(V * (log(堆大小) + E * log(堆大小)))
• O(V * ((E + 1) * log(堆大小)))
• O(V * (E * log(堆大小)))
• E = V 因为每个顶点都可以引用所有其他顶点
• O(V * (V * log(堆大小)))
• O(V^2 * log(堆大小))
• 堆大小是V^2因为我们每次想要更新距离时都会推送到它，并且每个顶点最多可以进行 V 次比较。例如，对于最后一个顶点，第一个顶点有距离10，第二个有9，第三个有8，等等，所以，我们每次都推送更新
• O(V^2 * log(V^2))
• O(V^2 * 2 * log(V))
• O(V^2 * log(V))
• V^2也是边的总数，所以如果我们让E = V^2（如官方命名），我们将得到O(E * log(V))

Answer 3

令 n 为顶点数，m 为边数。

由于使用 Dijkstra 算法您有 O(n) delete-min s 和 O(m) reduction_key s，每个成本 O(logn)，使用二元堆的总运行时间将为 O(log(n)(m + n)) . 完全有可能使用斐波那契堆将降低密钥的成本摊销到 O(1) 导致总运行时间为 O(nlogn+m) 但实际上这通常不会这样做，因为 FH 的常数因子惩罚非常大并且在随机图上，decrease_key的数量远低于其各自的上限（更多在 O(n*log(m/n) 的范围内，这在 m = O(n) 的稀疏图上更好）。因此，请始终注意总运行时间取决于您的数据结构和输入类这一事实。