设置联合操作的运行时间

Question

给定两组A和B，用于查找联合的常用算法是什么，它的运行时间是多少？

我的直觉：

a = set((1, 2, 3))
b = set((2, 3, 5))
union = set()
for el in a:
    union.add(el)

for el in b:
    union.add(el)

添加碰撞检查，即O（1），然后添加元素，即（??）。这样做了n次（其中n是| a | + | b |）。所以这是O（n * x），其中x是添加操作的平均运行时间。

这是对的吗？

Answer 1

这非常依赖于实现。其他人提到了基于可比较的集合（具有小于排序的集合）或hashables（具有用于散列的良好散列函数）。另一个可能的实现涉及<！>“union-find <！>”，它只支持常规设置操作的一个特殊子集但速度非常快（我认为联合是分摊的常量时间吗？），你可以在这里阅读它

http://en.wikipedia.org/wiki/Union_find

并在此处查看示例应用

http://lorgonblog.spaces.live.com/blog /cns!701679AD17B6D310!220.entry

Answer 2

添加/查找（碰撞）的复杂性取决于union的实现。

如果你正在使用一些基于哈希表的数据结构，那么假设一个好的哈希函数，你的碰撞操作确实是恒定的。

否则，对于已排序的列表/树数据结构，add可能是O（Log（N））。

Answer 3

第一个答案：如果您正在处理数字的集合，您可以将集合实现为不同元素的排序向量。然后你可以简单地将union（S1，S2）实现为合并操作（检查重复），这需要O（n）时间，其中n =基数之和。

现在，我的第一个答案有点天真。并且Akusete是对的：你可以，你应该将一个集合实现为一个哈希表（一个集合应该是一个通用的容器，而不是所有的对象都可以被排序！）。然后，搜索和插入都是O（1），并且，正如您所猜测的，联合需要O（n）时间。

（查看Python代码）Python集使用哈希表实现。阅读这个有趣的主题。另请参阅此实现，它使用已排序的向量。

Answer 4

如果你可以使用bitsets（int数组中的每个位等于你的一个项目），你可以简单地遍历int数组和OR元素。这具有复杂度O（N）（其中N是数组的长度）或O（（m + 31）/ 32）其中M是项目数。