algorithm - 在集合列表中查找不相交集合对的数量

Question

问题陈述如下:给定一个包含 n 个集合的列表，每个集合包含 k 个整数，找出不相交集合对的数量。假设集合中的可能元素是正的，并且以 c > n 为界，并且假设 k << n。

我正在尝试想出一个比 O(kn^2) 更快的高效算法来解决这个问题，O(kn^2) 是原始解决方案的运行时间。

我能想到的最佳策略涉及遍历列表中的每个集合，并对集合的元素进行散列处理，这样集合中的每个元素都映射到包含它的集合的一组索引。然后，对于迭代中的当前集合，使用它的 c 个元素作为键，并考虑哈希表作为值给出的 c 个索引集的并集。这个得到的索引集表示到目前为止遇到的与当前集合不相交的集合的数量，我们可以使用它来找到不相交的集合的数量。在整个迭代过程中对该值求和会​​得出正确答案。但是，由于并集运算的复杂度为 O(n)，因此该策略并不比原始解决方案好多少。

这个问题最有效的解决方案是什么？

Answer 1

对于 k << n，您可以通过以下方式降低复杂性:

• 对每个集合进行排序，可以是n * k * log(k)
• 然后按倒数第一个元素对所有集合进行排序，n * log(n)

现在比较需要n * (n - 1)次操作，分别是:

• 比较 s1.Last 和 s2.First(这应该是大多数情况，因为 k << n)
• 或者考虑到 s1 和 s2 已排序，有效地搜索 k 中最大的 s1 s2 交集