多组交集的算法模型

Question

我的问题是，我们如何为 5~7 组应用交集。假设每个集合都有一组元素。请帮助我为此创建一个算法，以及这个过程的复杂性。

Answer 1

一个简单的方法:

I = S_1;
For each set s in S_2 ... S_N:
    For each element ei in I:
      if ei not in s
        remove ei from I
      endif
    endfor
endfor

如果每个集合有 m 个元素并且有 N 个集合，则复杂度为 m^2xN。如果集合已排序，那么您可以通过二进制搜索获得 mlog(m)N，甚至可以通过在排序情况下推进两个迭代器来获得 O(mN)。