18

我发现 Prims 算法的时间复杂度无处不在O((V + E) log V) = E log V。但正如我们可以看到的算法：

时间复杂度似乎是O(V(log V + E log V))。但是如果它的时间复杂度是O((V + E) log V)。那么嵌套必须是这样的：

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

4

4 回答 4

40 
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)。

于 2014-01-15T08:48:21.860 回答
8

你的想法似乎是正确的。让我们将复杂性视为 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))

于 2016-03-07T13:26:25.963 回答
5

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？如果您只考虑我们必须检查每个 Vertex 及其邻居，并且在最坏的情况下，图表的邻居数接近 ，您可能会达到该术语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)。

于 2018-03-27T15:23:54.263 回答
2

实际上，正如您所说，for 嵌套在内部，而时间复杂度应该是 vE lg V 在渐近分析的情况下是正确的。但是在科门，他们已经做了摊销分析，这就是为什么它出来（Elogv）

于 2014-02-04T05:23:00.937 回答