algorithm - 并集算法

Question

我正在阅读著名的union-find 问题，这本书说：“find 或 union 都需要O(n)时间，而另一个需要O(1)....”

但是使用位串来表示集合呢？然后联合（使用位或）和查找（遍历集合列表检查相应的位是1）都将采用O(1)..

这个逻辑有什么问题？

Answer 1

这两个操作都可以在 的摊销时间内完成O(Alpha(n))，其中 Alpha 是一个inverse of the Ackermann function（增长非常缓慢）。您必须将问题表示为阿甘。选择某个子图的代表（树节点），联合操作将合并树（将较小的树挂在较高的根下方）。联合操作只是遍历到根并缩短遍历的路径（将搜索的元素（可能所有遍历的元素）挂在根下方）。

Answer 2

带有位域

• 联合将是 O(n)。您假设您可以or对两个本机整数做一些简单的操作，但如果 n 很大，您显然不能使用内置类型。
• 发现将是 O(1)。您不必迭代，您知道位的确切位置。

此外，位域并不真正适合任意集合。例如，如果您有一个可以包含任何 32 位整数的集合，您需要一个大小为 4G/8=0.5G 的位域。