logo标签列表

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

algorithmgraphbig-otime-complexitydijkstra
124
根据我的理解，使用下面给出的邻接列表计算Dijkstra算法的时间复杂度为大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)。为什么？

8个回答
142

Dijkstra最短路径算法的时间复杂度是O(ElogV)，其中：

  • V表示顶点数
  • E表示边的总数

你的分析是正确的，但符号的含义有所不同！你说算法的时间复杂度是O(VElogV)，其中：

  • V表示顶点数
  • E表示单个节点连接的最大边数。

让我们把你的E重新命名为N。因此，一个分析说O(ElogV)，另一个分析说O(VNlogV)。两者都是正确的，实际上E=O(VN)。区别在于ElogV是更紧密的估计。

6
谢谢，我明白了你的观点。adjacentEdges*totalVertices = totalEdges(E)。但是你能否解释一下更紧密的界限/估计意味着什么。 - Meena Chaudhary
8
更确切地说，maxAdjacentEdgesOfAVertex * totalVertices >= totalEdges 就是使得上限更紧的因素。更紧的上限意味着更接近真实值的估计。例如，如果一个算法执行了 n + 10 次操作，你可以说它是 O(n^2) 是正确的，或者是 O(nlogn) 也是正确的。但比这两个更紧的上限是 O(n)。最紧密的上限被称为 Θ，因此在上述示例中，n + 1 = Θ(n)。（Θ 的定义是既是上限又是下限） - Shahbaz
3
@SeldomNeedy，是的，这里的“log”是基于2的对数。虽然就大O符号而言，这并没有什么区别，因为"log10 = log10*log2"，所以差异只在一个常数上，这不会改变算法的时间复杂度顺序。 - Shahbaz
2
@SeldomNeedy，噢，而且在计算机算法中，你很少需要使用除2以外的任何底数的log函数，因此基数2有点被隐含了。 （看到我做的了吗？） - Shahbaz
6
我想指出，这个时间复杂度 O(E log V) 假设给定的图是连通的。例如，在有很多孤立顶点的稀疏图的情况下，它将不成立。这就是为什么 Dijkstra 的二叉堆实现的最坏情况是 O(V log V + E log V)。当我们不能假设 E >= V 时，它不能被降低到 O(E log V)。 - DBedrenko
显示剩余4条评论
22

为了更好地解释，我会提供更加详细的说明:

  • 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))
    • 1
    非常好的表达！ - Rishi
    2
    @MrA 如果你有顶点 A、B、C，那么 A 可以连接到 B 和 C。B 可以连接到 A 和 C。C 可以连接到 A 和 B。因此，任何一个顶点都可以连接到 V-1 个总顶点（除了它本身），所以每个顶点上可以有 V-1 条边，这基本上等于 V。因此，E=V。 - Sam
    讲解得很好！一个快速的问题 - 我们将 O(V^2 * log(V^2)) 简化为 O(E*log(V)) 而不是 O(E*log(E))，这是否有原因？我理解背后的数学，但不理解推理。 - LPR
    1
    @LPR技术上说，O(E*log(E))也是正确的，但O(E*log(V))更精确。而且OP特别询问了O(E*log(V))，所以在这种情况下我们必须使用它。 - Sam
    1
    非常感谢您。我对时间复杂度一直感到困惑。 - black.swordsman
    显示剩余4条评论
    10

    设n为顶点数量，m为边的数量。

    使用Dijkstra算法时，由于需要进行O(n)次delete-min以及O(m)次decrease_key操作，每次操作时间复杂度均为O(logn)，因此使用二叉堆的总运行时间为O(log(n)(m + n))。使用斐波那契堆可以将decrease_key操作的摊销成O(1)，从而使得总运行时间为O(nlogn+m)，但实践中通常不这样做，因为斐波那契堆的常数因子惩罚非常大，在随机图上decrease_key操作的次数远低于其上限（在稀疏图中约为O(n*log(m/n))），因此总运行时间既取决于数据结构，也取决于输入类型。

    3

    在稠密（或完全）图中，E logV > V^2。

    使用链接数据和二进制堆并不总是最好的选择。

    在这种情况下，我更喜欢仅使用矩阵数据并通过行节省最小长度。

    只需要V^2的时间。

    如果E < V / logV，或者每个顶点的最大边数小于某个常数K，则使用二叉堆。

    3
    我发现以以下方式来思考这个复杂性更容易：
    1. 首先将节点插入优先队列中，然后逐个提取节点，导致时间复杂度为 O(V log V)。 2. 一旦提取了一个节点，我们遍历其边并相应地更新优先队列。注意每条边只被探索一次，而且更新优先队列的时间复杂度为 O(log V)，从而导致总体时间复杂度为 O(E log V)。
    简而言之，你需要从优先队列中提取 V 次，并对优先队列进行 E 次更新，总体时间复杂度为 O((V + E) log V)。
    1
    假设优先队列中的节点数为 V。但是在“访问”节点之前，我们可以多次将相同的节点推入队列，这更像是 E 而不是 V？您是如何得出这个假设的？ - eriee
    1
    您可以参考以下实现：https://www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/。特别地，节点不会被添加两次到最小堆中，相反，它们的权重会被更新，并且它们在最小堆中的位置也会相应地更新。 - Niccolo Sacchi
    2
    @eriee，实际上你是对的，堆大小可以随着最大边界数增长，即v(v-1)，这是v^2。但log(v^2)是l2*log(v)，最终是log(v)。 - Ayyappa Gollu
    1

    • E 代表边，V 代表顶点。边的数量为

       (V *(V-1)) / 2

    大约

        V ^ 2

    • 因此，我们可以将最大的V ^ 2边添加到最小堆中。 因此，对最小堆中的元素进行排序需要

       O(Log(V ^ 2))

    • 每次我们将新元素插入最小堆时，都会进行排序。 我们将有E条边，因此我们将进行E次排序。 因此总时间复杂度为

      O(E * Log(V ^ 2)= O( 2 * E * Log(V))
    省略常数2：
     O( E * Log(V))
    1

    V: 顶点数， E: 总边数 假设图形密集 复杂度将是 O(V*logV) + O( (1+2+...+V)*logV)

    1+2+....+(V-1) = (v)*(v+1)/2 ~ V^2 ~ E，因为图形密集 所以复杂度将是 O(ElogV)。

    总和 1+2+...+ V 指的是：对于 G.adj[u] 中不属于 S 的每个顶点 v 如果您在提取顶点之前考虑 Q，则具有 V 个顶点，然后是 V-1，然后是 V-2 ...... 然后是 1。

    enter image description here

    1

    让我们尝试分析CLRS书中给出的算法。

    enter image description here

    第7行的for each循环： 对于任何一个顶点'u'，循环运行的次数等于'u'的相邻顶点数量。 每个节点的相邻顶点数量始终小于或等于图中的总边数。

    如果我们将V（因为第4行的while循环）和E（因为第7行的for each循环）视为输入，并计算复杂度为VElog(V)，则相当于假设每个顶点有E个与之关联的边，但实际上单个顶点上至多或少于E条边。（在内部顶点的星形图案例中会出现至多E个相邻顶点的情况）

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接