每对相同大小集合的最大基数交集

Question

我们有N个集合，每个集合都有N个整数。

我们取每一对集合，找到它们的交集S。

现在，我们有兴趣找出交集S的基数（cardinality），使其具有最大的基数。

---

示例 例如，假设N为4，并且我们有4个每个元素都有4个元素的集合：

A= {1,2,5,6}, B= {2,5,7,6}, C= {3,4,2,6}, D= {1,4,7,8}

现在我们对这些集合进行成对交集，并找到一个具有最大基数的交集S={2,5,6}。

因此，我们返回3。

---

可以使用Θ(N³)时间的暴力解决方案。我们可以用其他方法更高效地完成吗？

- Sushil Verma

Answer 1

以下情况可以减少运行时间，如果：

1. 存在一些α > 0，使得（对于固定的α和递增的n），有两个集合至少有α重叠部分。

2. 许多配对是不相交或几乎不相交的（稍后会更加精确地说明）。

3. 您愿意使用高概率蒙特卡罗算法（错误概率随n递减）。

假设您首先将每个集合转换为哈希表。这需要（期望的）Θ(n²)时间。现在对于每对集合（即，一个n²循环），从第一个集合中选择√n个随机元素，并计算第二个集合中的命中次数（期望O(√ n)时间）。

通过 乘法Chernoff界 和 并集界 的组合，您可以仅保留命中次数至少为 1/2 α √ n 的成对数据。

因此，很有可能将 n² 对数据缩小到一些 β n² 对，时间复杂度仅为 O(n^2.5)。从这里开始使用暴力方法来继续处理。这取决于 β 如何随着 n 的增长而变化，可能对您有用或无用。

- Ami Tavory