Bet*_*moo 2 algorithm time-complexity union-find
我正在阅读有关着名的工会发现问题,而且这本书说:"无论是发现还是工会需要O(n)时间,而另一个需要O(1)......"
但是如何使用位串来表示集合呢？然后两个联合(使用位OR)和查找(迭代通过集合列表检查相应的位是1)将采取O(1)..
这个逻辑出了什么问题？
这两个操作都可以在摊销的时间内完成O(Alpha(n)),其中Alpha是一个inverse of the Ackermann function(增长非常缓慢).你必须将问题表示为福雷斯特.选择某个子图(树节点)的代表,并且联合操作将合并树(将较小的树挂在较高的根下面).union操作只是遍历到根并缩短遍历的路径(将搜索的元素(可能是所有遍历的元素)挂起在根目录下).