检查集合A是否是集合B的子集的算法，时间复杂度快于线性时间

Question

6

是否有一种算法（最好是常数时间）可以检查集合A是否是集合B的子集？

创建数据结构以便解决此问题不会影响运行时间。

- volni

1

找到了这个答案：https://dev59.com/23M_5IYBdhLWcg3wiDuA#1338515 - volni

1

我们需要更多关于集合内容的信息。通用算法无法给出恒定的时间复杂度。至少我所知道的没有这样的算法。 - Samy Arous

集合元素是字符串，但是我们当然可以通过一些哈希函数或者将它们分配到位集中的位置来实现更快的算法。 - volni

如果你有有关这些字符串的更多信息，可能会更容易地利用它们的某些特点。 - argentage

3个回答

0

你可以尝试布隆过滤器（http://en.wikipedia.org/wiki/Bloom_filter）。但是可能会出现误判，可以通过Keith上面提到的方法来解决（但请注意，哈希的最坏情况复杂度不是O（n），而是可以做到O（nlogn））。

- ElKamina

我喜欢这个算法，因为在我的情况下进行一些后处理非常快速。布隆过滤器将在服务器上运行，结果集的后处理将在客户端运行。 - volni

0

如果你有一个字符串集中最不常见的字母和字母对的列表，你可以将你的集合按它们的最不常见的字母和字母对排序存储，并尽可能快地丢弃负匹配以最大化匹配效率。我不太清楚这与布隆过滤器的结合程度如何，也许哈希表会更好，因为二元组和字母并不是很多。

如果你有一些关于子集的最大大小甚至是普遍大小的信息，那么你可以类似地通过把所有给定大小的子集放入一个布隆过滤器中来预处理数据。

你也可以两者都结合使用。

- argentage

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Keith Randall · Accepted Answer

嗯，你需要查看A的每个元素，因此它至少需要与A的大小成线性时间。

使用哈希表（将B的元素存储在哈希表中，然后查找A的每个元素），可以轻松实现O(A+B)算法。除非你知道一些关于B的高级结构，否则我认为你无法做得更好。例如，如果B按排序顺序存储，则可以使用二分查找进行O(A log B)。