set union 操作的运行时间

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

add/find(collision) 的复杂性取决于 union 的实现。

如果您正在使用一些基于哈希表的数据结构，那么假设一个好的哈希函数，您的碰撞操作确实会保持不变。

否则，对于排序列表/树数据结构，添加可能是 O(Log(N))。

Answer 2

这在很大程度上取决于实现。其他人提到了基于可比较的集合（具有用于排序的小于）或可散列（具有良好的散列函数用于散列）。另一种可能的实现涉及“union-find”，它仅支持常用集合操作的专门子集，但速度非常快（我认为联合是摊销常数时间？），您可以在这里阅读它

并在此处查看示例应用程序