algorithm - 用于检查集合 A 是否是集合 B 的子集的算法，比线性时间快

Question

是否有一种算法（最好是恒定时间）来检查集合 A 是否是集合 B 的子集？

创建数据结构来解决这个问题不计入运行时。

Answer 1

好吧，您将不得不查看 的每个元素A，因此它必须至少是 的大小的线性时间A。

O(A+B)算法很容易使用哈希表（将 的元素存储在B哈希表中，然后查找 的每个元素A）。我不认为你可以做得更好，除非你知道一些先进的结构B。例如，如果B按排序顺序存储，则可以O(A log B)使用二进制搜索。

Answer 2

您可能会选择布隆过滤器（http://en.wikipedia.org/wiki/Bloom_filter）。但是可能存在误报，可以通过上面 Keith 提到的方法解决（但请注意，散列的最坏情况复杂度不是 O(n)，但您可以执行 O(nlogn)。

1. 根据Bloom filter判断A是否是B的子集
2. 如果是，那么做一个彻底的检查

Answer 3

如果你有一个字符串集中最不常见的字母和字母对的列表，你可以存储你的集合，按照它们最不常见的字母和字母对排序，并尽可能快地排除负面匹配的机会。我不清楚这与布隆过滤器结合起来有多好，可能哈希表会做，因为没有太多的二字和字母。

如果您有一些关于子集的最大大小甚至是公共大小的信息，您可以通过将给定大小的所有子集放入前面提到的布隆过滤器来类似地预处理数据。

您也可以将这两者结合起来。