Prims算法的时间复杂度？

Question

我发现普里姆算法的时间复杂度为到处O((V + E)登录V)= E日志V.但是我们可以看到算法:

似乎时间复杂度为O(V(log V + E log V)).但如果其时间复杂度为O((V + E)log V).那么嵌套必须是这样的:

但上面的嵌套似乎是错误的.

Answer 1

MST-PRIM(G, w, r)
1  for each u ? G.V
2       u.key ? ?
3       u.? ? NIL
4   r.key ? 0
5   Q ? G.V
6   while Q ? Ø
7       u ? EXTRACT-MIN(Q)
8       for each v ? G.Adjacent[u]
9           if v ? Q and w(u, v) < v.key
10              v.? ? u
11              v.key ? w(u, v)

使用二进制堆

1. 一次调用所需的时间复杂度EXTRACT-MIN(Q)是O(log V)使用最小优先级队列.第6行的while循环执行总V 次.EXTRACT-MIN(Q)所以称为V次.所以复杂性EXTRACT-MIN(Q)是O(V logV).

2. 第for8行的循环执行总2E时间,因为每个邻接列表的长度是2E针对无向图的.执行第11行所需的时间是O(log v)使用DECREASE_KEY最小堆上的操作.第11行也执行总2E时间.所以执行第11行所需的总时间是O(2E logV) = O(E logV).

3. 第for1行的循环将执行V一次.使用该过程执行第1行到第5行将需要复杂性O(V).

总时间复杂度MST-PRIM是执行步骤1到3所需的时间复杂度的总和O(VlogV + (E logV + V) = O(E logV).

使用斐波那契堆

1. 与上述相同.
2. 执行第11行需要O(1)摊销时间.第11行总共执行一次2E.所以总的时间复杂度是O(E).
3. 与上述相同

因此,总时间复杂度MST-PRIM是执行步骤1到3的总和,用于总复杂度O(V logV + E + V)=O(E + V logV).

Answer 2

你的想法似乎是正确的。让我们把复杂度当作 V(lg(v) + E(lg(v))) 然后注意，在内部 for 循环中，我们实际上是通过所有的顶点，而不是边缘，所以让我们稍微修改一下， V(lg(v) + V(lg(v))) 这意味着 V(lg(v)) + V*V(lg(v)) 但是对于最坏的情况分析（密集图），V*V 是大致等于边数 E V(lg(v)) + E(lg(v)) (V+E((lg(v)) 但由于V << E，因此 E(lg(v))

Answer 3

Prim 算法的时间复杂度为 O(VlogV + ElogV)。看起来你明白它是怎么VlogV来的，所以让我们跳过它。那么ElogV从何而来呢？我们先来看看 Prim 算法的源码：

  | MST-PRIM(Graph, weights, r)
1 |  for each u ? Graph.V
2 |       u.key ? ?
3 |       u.? ? NIL
4 |   r.key ? 0
5 |   Q ? Graph.V
6 |   while Q ? Ø
7 |       u ? EXTRACT-MIN(Q)
8 |       for each v ? Graph.Adj[u]
9 |           if v ? Q and weights(u, v) < v.key
10|               v.? ? u
11|               v.key ? weights(u, v)

第 8-11 行对 中的每个元素执行Q，我们知道有V元素在Q（代表所有顶点的集合）。第 8 行的循环遍历当前提取的顶点的所有邻居；我们将对下一个提取的顶点以及之后的顶点执行相同的操作。Djistkra 算法不重复顶点（因为它是一种贪婪的最优算法），并且最终会让我们遍历每个连接的顶点，探索它们的所有邻居。换句话说，这个循环最终会在某个点 ( 2E)两次遍历图的所有边。

为什么两次？因为在某些时候，我们会从另一个方向回到先前探索过的边缘，并且在我们实际检查之前我们不能排除它。幸运的是，这个常数2在我们的时间复杂度分析中被删除了，所以循环实际上只是E做了大量的工作。

为什么不是V*V？如果您只是考虑到我们必须检查每个顶点及其邻居，并且在最坏的情况下，邻居的数量接近 ，那么您可能会达到该术语V。事实上，在一个密集的图中V*V = E。但是对这两个循环的工作更准确的描述是“遍历所有边两次”，所以我们E改为引用。读者可以将他们的图的稀疏程度与该术语的时间复杂度联系起来。

让我们看一个有 4 个顶点的小示例图：

    1--2
    |\ |
    | \|
    3--4

假设这Q将为我们提供顺序为 1、2、3 和 4 的节点。

• 在外循环的第一次迭代中，内循环将运行 3 次（分别为 2、3 和 4）。
• 在外循环的第二次迭代中，内循环运行了 2 次（对于 1 和 4）。
• 在外循环的第三次迭代中，内循环运行了 2 次（分别为 1 和 4）。
• 在外循环的最后一次迭代中，内循环运行了 3 次（分别为 1、2 和 3）。

总迭代次数为 10，这是边数 ( 2*5) 的两倍。

提取最小值并跟踪更新的最小边（通常使用斐波那契堆完成，导致log(V)时间复杂性）发生在循环迭代内部 - 确切的机制涉及最终需要在内循环内发生足够多的时间，以便它们受时间控制两个循环的复杂性。因此，该算法阶段的完整时间复杂度为O(2*E*log(V))。放弃不变的收益O(E*log(V))。

鉴于算法的总时间复杂度为O(VlogV + ElogV)，我们可以简化为O((V+E)logV)。在一个稠密的图中E > V，我们可以得出结论O(ElogV)。