algorithm - 集合并集运算的运行时间

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 是添加操作的平均运行时间。

它是否正确？

score 5 · Accepted Answer

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

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

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

score 4 · Accepted Answer

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

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

（查看您的 Python 代码）Python 集是使用哈希表实现的。通读这个有趣的线程。另请参阅这个使用排序向量的实现。

score 3 · Accepted Answer

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

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

score 0 · Accepted Answer

如果您可以使用位集（int 数组中的每个位都等于您的集合中的一项），您可以简单地遍历 int 数组并对元素进行 OR。这具有复杂性 O(N)（其中 N 是数组的长度）或 O((m+31)/32)，其中 M 是项目数。

4 回答 4