并查算法
我正在阅读著名的并集查找问题，书中写道：“查找或并集将花费 O(n) 时间，而另一个则需要 O(n) 时间。将需要O(1)......”
但是使用位串来表示集合怎么样？ 那么 union（使用位 OR）和 find（遍历集合列表检查相应位是否为 1）都将花费 O(1)..
这个逻辑有什么问题？
I was reading about the famous union-find problem, and the book was saying: "either the find or the union will take O(n) time, and the other one will take O(1)...."
But what about using bit strings to represent the set?
Then both union (using bit OR) and find (iterating through set lists checking the corresponding bit is 1) will take O(1)..
What is wrong with that logic?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这两个操作都可以在
O(Alpha(n))的平摊时间内完成，其中 Alpha 是阿克曼函数的反函数（增长非常< /em> 慢慢地）。你必须将问题表示为福雷斯特。选择某个子图（树节点）的代表，并集操作将合并树（将较小的树挂在较高的树的根下方）。并集操作只是遍历到根并缩短遍历的路径（将搜索到的元素（可能是所有遍历的元素）挂在根下方）。Both operations can be done in amortized time of
O(Alpha(n)), where Alpha is aninverse of the Ackermann function(grows very slowly). You have to represent the problem as a forrest. Choose a representative of some subgraph (tree node) and the union operation will merge the trees (hang the smaller tree below the root of the higher). The union operation simply traverses to the root AND shorthens the traversed path (hangs the searched element (possibly all traversed elements) below the root).使用位域
or操作，但如果 n 很大，则显然不能使用内置类型。此外，位域并不真正适合任意集。例如，如果您有一个可以包含任何 32 位整数的集合，则需要一个大小为 4G/8=0.5G 的位域。
With a bitfield
oron two native integers but if n is large you obviously cannot use builtin types.Also, a bitfield is not really suited for arbitrary sets. For example if you have a set that can contain any 32bit integer, you need a bitfield with a size of 4G/8=0.5G.