n個の自然数の集合、S_1,S_2,S_3,,,S_nが与えられているとします。
この時、i!=j , S_i ⊆ S_j となる i,jが存在するか?という問題を考えます。
素朴な方法ではそれぞれの集合のペアの包含関係を調べることになると思いますが、
この時、集合の包含関係をO(n^2)回調べる必要があります。
この回数を減らす方法はあるでしょうか?
n個の集合の包含関係
Jogenara
- 664
- 10
- 19