algorithm - Prim 的 MST 算法的时间复杂度

Question

有人可以向我解释为什么使用相邻矩阵的 Prim 算法导致时间复杂度为 O(V<sup>2</sup>) ？

Answer 1

(对于看起来草率的 ASCII 数学提前抱歉，我认为我们不能使用 LaTEX 来排版答案)

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

这样，我们只检查 distance 来找到下一个目标，因为我们这样做了 V 次并且 distance 有 V 个成员，所以我们的复杂度是 O(V^2)。

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

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

证明:

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

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

在最坏的情况下，每个节点都包含到树中每个节点的连接，导致 n * (V-n) 条边和 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)

QED