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