big-theta - 在此算法中找不到 findset 的运行时间

Question

我设计了一个算法，我试图找到能够得出θ的上限和下限：

ms(G,w)
for each v in G
      make-set(v)
sort the edges of G.E into non-decreasing order by weight
if(find-set(v) not equal to find-set(u))
     union(u,v)
else
     feed=feed U {edge(u,v)}

如您所见，它与 kruskal 算法非常相似。这里我的问题是我无法理解 find-set 的运行时间

对于另一部分，我有：

makeset O(v) 排序 O(ElogE) union O(1) 但是对于 find set 我不知道如何计算它？（你能告诉我计算的 union 运行时间是否为真）

Answer 1

find-set 的大 O 取决于使用的实现。

例如，以集合中的数据数组为例。它们是排序的，您可以使用 O(log(N)) （甚至 O(log(log(N)) 访问它们，但是任何插入都是 O(N) - 考虑将一个新的最低元素添加到我们的设置。您可以通过使用堆来改善这一点。

或者您将集合存储在链接列表中。添加和删​​除是 O(1)，但要找到它，您必须遍历所有条目，因此 O(N)。

您必须决定哪个操作更频繁使用，或者在算法的更关键点使用。