检查集合A是否为集合B的子集的算法比线性时间快

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

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

最佳答案

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

使用哈希表很容易实现O(A+B)算法(将B的元素存储在哈希表中，然后查找A的每个元素)。我认为除非您知道B的一些高级结构，否则您无法做得更好。例如，如果按排序顺序存储了B，则可以使用二进制搜索来执行O(A log B)。