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

问题描述

根据我的理解，我已经使用下面给出的邻接列表计算了Dijkstra算法的时间复杂度为大O符号。它并没有按照它应有的原理出现，并且让我逐步了解它。

1. 每个顶点都可以连接到（V-1）个顶点，因此每个顶点的相邻边的数量为V-1。让我们假设E代表连接到每个顶点的V-1个边。 在min堆中更新每个相邻顶点的权重为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） where ：

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

  您的分析是正确的，但你的符号有不同的含义！您说算法是 O（VElogV）其中：
  
  

  
  
  • V 是顶点的数量
    
  • E 是连接到单个物体的最大边数
  
  
  
  
  

  让我们将您的 E 重命名为 N 。因此，一个分析称 O（ElogV），另一个分析称 O（VNlogV）。两者都是正确的，事实上 E = O（VN）。区别在于 ElogV 是一个更紧的估计。

  
  

  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. Each vertex can be connected to (V-1) vertices, hence the number of adjacent edges to each vertex is V - 1. Let us say E represents V-1 edges connected to each vertex.
  2. Finding & Updating each adjacent vertex's weight in min heap is O(log(V)) + O(1) or O(log(V)).
  3. Hence from step1 and step2 above, the time complexity for updating all adjacent vertices of a vertex is E*(logV). or E*logV.
  4. Hence time complexity for all V vertices is V * (E*logV) i.e O(VElogV).

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

  解决方案

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

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

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

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

  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屋！