26

我正在计算这样的 kruskal 算法的时间复杂度（请参阅附件中的算法）

T(n) = O(1) + O(V) + O(E log E) + O(V log V)
     = O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E + E log E
     = E log E

CLRS 算法：

在此处输入图像描述

是正确的还是我做错了什么，请告诉。

4

6 回答 6

18

克鲁斯卡尔是 O(E log E); 你的推导是正确的。你也可以说 O(E log V) 因为 E <= V * V, 所以 log(E) <= 2 log(V) （我不知道为什么我记得那个，除了我认为教授说在一次考试中......）

于 2013-12-06T20:29:38.787 回答
5

由于 |V| > |E|+1，我们更喜欢使用 V 项而不是 E 项的严格上限。

    |E| <= |V|²   
.   log |E| < log |V|²   
.   log |E| < 2 log |V| 
.   running time of MST-KRUSKAL is: O(E log V)
于 2014-11-04T20:16:47.253 回答
2

这么晚才回复很抱歉。
Kruskal 算法的运行时间是 O(E log E) 而不是 O(E log V)。

因为，必须首先对边进行排序，并且需要 O(E log E)，它在运行时中占主导地位，以验证所考虑的边是否是安全边，这将花费 O(E log V)。和 |E| > |V|((如果图已经是一棵树，则为极端情况))，因此可以安全地假设运行时为 O(E log E)

于 2015-04-05T17:32:15.760 回答
2

O(ElogE) 肯定是 O(ElogV) 因为 E <= V^2 （全连接图）

ElogE <= Elog(V^2) = 2ElogV = O(ElogV)

于 2020-12-05T00:34:30.537 回答
1

所有其他答案都是正确的，但我们可以考虑以下情况，这给了我们O(|E|)的时间复杂度。
以下答案来自Dasgupta 的算法书，第 5 章，第 140 页，部分路径压缩：
在该算法的时间复杂度计算中，主要部分是边缘排序部分，即O(|E| log|E|)或正如所有其他答案所解释的那样 O(|E|.log|V|)。

但是，如果给定的边是排序的呢？
或者如果权重很小（比如 O(|E|)），那么排序可以在线性时间内完成（比如应用计数排序）。
在这种情况下，数据结构部分成为瓶颈（Union-find），考虑将其性能提高到每个操作的 log n 之外是有用的。解决方案是使用路径压缩方法，同时执行 find() 操作。 这个摊销成本仅略高于 O(1)，低于早期的 O(log n)。有关更多详细信息，请查看此参考在此处输入图像描述

. 简单的想法是，每当调用 find(v) 操作来查找 v 所属的集合的根时，所有节点到其父节点的链接都将改变并指向根。这样，如果您在同一路径上的每个节点 x 上调用 find(x) 操作，您将在 O(1) 中获得集合的根（标签）。因此，在这种情况下，算法瓶颈是联合查找操作，使用所描述的解决方案是 O(1)，该算法在所描述情况下的运行时间是 O(|E|)。

于 2019-03-25T07:23:44.127 回答
0

第 5 到 9 行，复杂度为 O(E)。

  1. O(E)
  2. O(1)
  3. O(1)
  4. O(1)
  5. O(1)

直到第 5 行，您已经正确计算了复杂性。最后，这里的主导因素是 O(E lg E)。所以，复杂度是 O(E lg E)

于 2018-02-12T16:33:26.123 回答