5

在作为特定集合的子集的有限集合中找到集合的最佳算法是什么？

例如，如果

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

X ={1, 2, 3, 5}

那么，A 和 C 是 X 的子集。

有没有一种算法可以以线性时间复杂度做到这一点？

实现注意：集合的成员通常来自非常有限的范围，因此，使用 C++ bitset 来实现算法可能是一个好主意。不能吗？

编辑：集合中的集合数量通常非常大于 X 中的元素数量（在示例中）。有没有办法根据 X 中的元素数量来做到这一点？可能使用哈希或其他东西？

4

2 回答 2

7

让我们暂时假设 64 个可能的元素。

那么，如果将每个元素表示为一个位，则可以使用一个 64 位长的整数来表示每个集合，那么：a & b是 和的集合 交集。如果（且仅当）是then的子集。ab
aba & b == a

当然，如果您需要超过 64 位，您可以使用 bitset。

对于大范围的元素，可以使用哈希表存储（一次）超集，然后迭代潜在的子集以检查是否所有元素都在其中。
它在输入大小中是线性的（平均情况）。

编辑：（回复已编辑的问题）

除非您预先存储了一些有关数据的信息 - 否则无法做到最好O(|X| + n*min{m,|X|})Where |X| 是集合 X 的大小， 是集合n的数量， 是集合m的平均大小。
这样做的原因是因为在最坏的情况下，您需要读取所有集合中的所有元素（因为您为每个集合读取的最后一个元素决定了它是否是子集），因此如果没有先前的知识，我们将无法取得更好的效果套。

建议的解决方案是：
Bitset：O(|X|*n)
哈希解决方案：（O(|X| + min{m,|X|}*n)平均情况）

尽管散列解决方案提供了更好的渐近复杂度，但对于位集来说，常数要好得多——因此位集解决方案可能会更快|X|

于 2012-09-24T06:32:54.917 回答
1

如果您没有时间限制来构建一些额外的结构，那么 O(log(n)) 解决方案是将代表个体集的位序列存储在Trie中。

您不必像 Amit 所假设的那样将您的集合（也称为位串）与所有其他集合进行比较。如果您有一个排序的位串集合，那么每次比较显然会将变体的数量减少一半。是的，当然，构建 bitset trie 的时间类似于 O(n*log(n))，但它是一个预处理。

于 2012-09-24T08:30:12.437 回答