找不到运行findset的时间在这个算法

我设计一个算法，我想找到的上界和下界为能够断定THETA：找不到运行findset的时间在这个算法

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算法。在这里我的问题是我无法理解的发现设置

的运行时间的另一部分，我有：

makeset O（V）排序O（ElogE）工会O（1）但对于查找集我不知道如何计算它？（也可以告诉我，如果联盟的计算运行时间为真）

来源

2014-03-02 Hamed Minaee

查找集的大O取决于所使用的实现。

举一个例子，在你的数据集中取一个数组。它们是排序的，你可以用O（log（N））（或者甚至O（log（log（N））访问它们，但是任何插入都是O（N） - 考虑你为我们添加一个新的最低元素你可以通过使用堆来改进它

或者你把这个集合存储在一个链表中，添加和删除是O（1），但是为了找到它，你必须遍历所有的条目，因此O（ N）。

你必须决定，该操作被用于更多的时候还是在你的算法的一个比较关键的一点。

来源

2014-03-02 18:44:04 usr1234567

感谢yesyou是对的，我读了CONTEX的它说，如果我使用分离集需要日志（五），但我仍然不明白为什么登录？ –

@HamedMinaee看看维基百科的文章http ：//en.wikipedia.org/wiki/Disjoint-set_data_structure – usr1234567

找不到运行findset的时间在这个算法

回答

相关问题