Skip to main content
本文に 12 文字追加; タイトルを編集
ソース リンク
cubick
  • 2.1万
  • 5
  • 27
  • 64

n個の集合の包含関係を求める計算量を減らすには?

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個の集合の包含関係

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

n個の集合の包含関係を求める計算量を減らすには?

n個の自然数の集合 S_1, S_2, S_3, ... S_n与えられているとします。
この時、i!=j , S_i ⊆ S_j となる i, j が存在するか?という問題を考えます。

素朴な方法ではそれぞれの集合のペアの包含関係を調べることになると思いますが、
この時、集合の包含関係を O(n^2) 回調べる必要があります。
この回数を減らす方法はあるでしょうか?

ソース リンク
Jogenara
  • 664
  • 10
  • 19

n個の集合の包含関係

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