algorithm - 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 的实现。

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

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