2

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

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

2
  • 回数を減らすだけなら「要素数の多い集合」⊆「要素数の少ない集合」をカットすることで減らせそう(集合の要素数でソートしておけばi<jだけ調べればOK)ですが、そうではなく計算量を減らしたい?(多分この案の比較回数はn(n-1)/2で、計算量としてはO(n^2)のまま)
    – Ripple
    Commented 5月14日 14:06
  • 欲を言えばオーダーが減るレベルで改善したいですが、この際、定数倍の改善も歓迎です。ありがとうございます。
    – Jogenara
    Commented 5月15日 2:45

0

この質問に回答するには、ログインする必要があります。

のタグが付いた他の質問を参照する。