Kruskal算法的时间复杂度？

Question

我正在计算像这样的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算法：

这是正确的还是我做错了请告诉我。

Answer 1

Kruskal是O（E log E）;你的推导是对的。你也可以说O（E log V），因为E <= V * V，所以log（E）<= 2 log（V）（我不知道为什么我记得那个，除此之外我认为一个教授放了那个在一次考试...）

Answer 2

自| 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)

Answer 3

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

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

Answer 4

第5到9行的复杂性是O（E）。

5. O（E）
6. O（1）
7. O（1）
8. O（1）
9. O（1）

直到第5行，你已经正确地计算了复杂性。最后，这里的支配因子是O（E lg E）。所以，复杂性是O（E lg E）

Answer 5

所有其他答案都是正确的，但我们可以考虑以下情况，它给出了O（| E |）的时间复杂度。 以下答案来自Algorithms book by Dasgupta，第5章，第140页，路径压缩部分： 在该算法的时间复杂度计算中，主要部分是边缘排序部分，其为O（| E | log | E |）或所有其他解释为O（| E | .log | V |）。 但是，如果给定的边缘被排序怎么办？ 或者，如果权重很小（例如，O（| E |）），那么排序可以在线性时间内完成（如应用counting sort）。 在这种情况下，数据结构部分成为瓶颈（Union-find），考虑提高每个操作的log n之外的性能是有用的。解决方案是使用路径压缩方法，同时执行find（）操作。 从早期的O（log n）开始，这个摊销的成本仅仅是O（1）。有关详细信息，请查看this reference。简单的想法是，每当调用find（v）操作来查找v所属的集合的根时，所有节点到其父节点的链接都将被更改并指向根节点。这样，如果在同一路径上的每个节点x上调用find（x）操作，您将在O（1）中获得集合的根（标签）。因此，在这种情况下，算法瓶颈是联合查找操作，并且使用所描述的解决方案是O（1），该算法在所描述的情况下的运行时间是O（| E |）。