5

有人可以向我解释为什么使用相邻矩阵的 Prim 算法会导致时间复杂度为0 吗？O(V2)

4

3 回答 3

6

（抱歉，ASCII 数学看起来很草率，我认为我们不能使用 LaTEX 来排版答案）

实现 Prim 算法O(V^2)复杂性的传统方法是除了邻接矩阵之外还有一个数组，让我们称它为distance该顶点到节点的最小距离。

这样，我们只检查distance找到下一个目标，并且由于我们这样做 V 次并且有 V 个成员distance，我们的复杂性是O(V^2)。

这本身是不够的，因为原始值distance很快就会过时。要更新这个数组，我们所做的就是在每一步结束时，遍历我们的邻接矩阵并distance适当地更新。这不会影响我们的时间复杂度，因为它仅仅意味着每一步都需要O(V+V) = O(2V) = O(V). 因此我们的算法是O(V^2)。

如果不使用distance，我们必须每次遍历所有 E 边，最坏的情况是包含 V^2 边，这意味着我们的时间复杂度为O(V^3).

证明：

为了证明没有distance数组就不可能及时计算 MST O(V^2)，请考虑在每次使用大小为 的树的迭代中n，都有V-n可能添加的顶点。

要计算选择哪一个，我们必须检查每一个以找到它们与树的最小距离，然后将其相互比较并找到那里的最小值。

在最坏的情况下，每个节点都包含与树中每个节点的连接，导致 n * (Vn) 条边和O(n(V-n)).

由于我们的总数将是当 n 从 1 到 V 时每个步骤的总和，所以我们的最终时间复杂度是：

(sum O(n(V-n)) as n = 1 to V) =  O(1/6(V-1) V (V+1)) = O(V^3)

量子点

于 2012-10-30T05:17:29.143 回答
6

注意：这个答案只是借用了jozefg的答案并试图更充分地解释它，因为我在理解之前必须考虑一下。

背景

图的邻接矩阵表示构造了一个 V x V 矩阵（其中 V 是顶点数）。单元格 (a, b) 的值是连接顶点 a 和 b 的边的权重，如果没有边则为零。

Adjacency Matrix

   A B C D E
--------------
A  0 1 0 3 2
B  1 0 0 0 2
C  0 0 0 4 3
D  3 0 4 0 1
E  2 2 3 1 0

Prim's Algorithm是一种算法，它采用图和起始节点，并在图上找到最小生成树 - 即它找到边的子集，以便结果是包含所有节点和组合边的树权重被最小化。可以总结如下：

  1. 将起始节点放在树中。
  2. 重复直到所有节点都在树中：
    1. 找到将树中的节点连接到树中的节点的所有边。
    2. 在这些边缘中，选择一个重量最小的边缘。
    3. 将该边和连接的节点添加到树中。

分析

我们现在可以开始分析算法，如下所示：

  1. 在循环的每次迭代中，我们向树中添加一个节点。由于有 V 个节点，因此该循环有 O(V) 次迭代。
  2. 在循环的每次迭代中，我们需要在树中找到并测试边。如果有 E 条边，朴素搜索实现使用 O(E) 来找到权重最小的边。
  3. 所以结合起来，我们应该期望复杂度是 O(VE)，在最坏的情况下可能是 O(V^3)。

然而，jozefg 给出了一个很好的答案来展示如何实现 O(V^2) 复杂度。

Distance to Tree

            | A  B  C  D  E
            |----------------
Iteration 0 | 0  1* #  3  2
          1 | 0  0  #  3  2*
          2 | 0  0  4  1* 0
          3 | 0  0  3* 0  0
          4 | 0  0  0  0  0

NB. # = infinity (not connected to tree)
    * = minimum weight edge in this iteration

这里距离向量表示将每个节点连接到树的最小加权边，使用如下：

  1. 使用复杂度 O(V) 到起始节点 A 的边缘权重进行初始化。
  2. 要找到下一个要添加的节点，只需找到距离的最小元素（并将其从列表中删除）。这是 O(V)。
  3. 添加一个新节点后，有 O(V) 条新边将树连接到其余节点；对于这些中的每一个，确定新边的权重是否小于现有距离。如果是，更新距离向量。再次，O（V）。

使用这三个步骤将搜索时间从 O(E) 减少到 O(V)，并增加了一个额外的 O(V) 步骤来在每次迭代时更新距离向量。由于现在每次迭代都是 O(V)，因此总体复杂度是 O(V^2)。

于 2012-10-30T05:49:10.333 回答
0

首先，显然至少是 O(V^2)，因为这就是邻接矩阵的大小。

查看http://en.wikipedia.org/wiki/Prim%27s_algorithm，您需要执行步骤“重复直到 Vnew = V”V 次。

在该步骤中，您需要计算出 V 中的任何顶点与 V 之外的任何顶点之间的最短链接。维护一个大小为 V 的数组，为每个顶点保存无穷大（如果顶点在 V 中）或最短的长度V 中的任何顶点和那个顶点之间的链接，以及它的长度（所以一开始这只是来自起始顶点和每个其他顶点之间的链接长度）。要找到下一个要添加到 V 的顶点，只需搜索这个数组，成本为 V。一旦你有了一个新顶点，查看从该顶点到每个其他顶点的所有链接，看看它们中是否有从 V 到的较短链接那个顶点。如果有，请更新数组。这也花费了V。

因此，您有 V 个步骤（要添加的 V 个顶点），每个步骤花费 V，这给您 O(V^2)

于 2012-10-30T05:27:45.063 回答