Prims算法的时间复杂度？

问题描述 投票：9回答：4

我发现Prims算法的时间复杂度到处为O（（V + E）log V）= E log V.但是我们可以看到算法：

似乎时间复杂度为O（V（log V + E log V））。但如果其时间复杂度为O（（V + E）log V）。那么嵌套必须是这样的：

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

time-complexity prims-algorithm
4个回答
27
投票
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. 第8行的for循环执行总2E次，因为对于无向图，每个邻接列表的长度是2E。通过在最小堆上使用O(log v)操作，执行第11行所需的时间是DECREASE_KEY。第11行也执行总2E次。所以执行第11行所需的总时间是O(2E logV) = O(E logV)。
  3. 第1行的for循环将执行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)的总复杂度。

3
投票

你的想法似乎是对的。让我们把复杂性当作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))

2
投票

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)

对Q中的每个元素执行第8-11行，我们知道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)。

1
投票

实际上正如你所说的那样嵌套在里面，而时间复杂度应该是v.E lg V在渐近分析的情况下是正确的。但是在cormen他们做了摊销分析，这就是为什么它出来（Elogv）

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.