セットAがセットBのサブセットであるかどうかをチェックするためのアルゴリズム

Question

セットAがセットBのサブセットであるかどうかをチェックするアルゴリズムがありますか？

この問題を解決するためにデータ構造を作成しても、ランタイムにはカウントされません。

Answer 1

これは、Aの各要素を調べる必要があるため、少なくともAのサイズの線形時間である必要があります。

ハッシュテーブル（ハッシュテーブルにBという要素を格納してから、各要素を検索してAを検索する）を使用するとアルゴリズムが簡単です。私はあなたがBのいくつかの先進的な構造を知らない限り、あなたはどんなこともできるとは思わない。たとえば、Bがソート順に格納されている場合、バイナリ検索を使用してO(A log B)を実行できます。

Answer 2

ブルームフィルタ（http://en.wikipedia.org/wiki/Bloom_filter）に行くかもしれません。しかし、そこの上にキースが言及した方法によって対処することができます偽陽性、あること（ただし、ハッシュの最悪の場合の複雑さはO（n）とされていませんが、あなたはO（nlogn）。

1. を行うことができますことに注意してくださいかもしれませんあなたができる、AがYESの場合
2. をブルームフィルタによるBの部分集合であるならば、あなたの文字列のセット内の文字の最小共通文字とペアのリストを持っている場合は、完全なチェック

Answer 3

を行う参照してください。最も一般的な文字と文字のペアでソートされたセットを保存し、できるだけ早くネガティブマッチを捨てる機会を最大限に活用してください。 これがブルームフィルタとどのくらいうまく組み合わされるかは分かりません。おそらく、多くのデグラムと文字がないため、ハッシュテーブルが実行します。

サブセットの最大サイズや共通サイズについての情報がある場合は、同じサイズのサブセットをすべて前述のようにブルームフィルタに入れることで同様にデータを事前処理できます。

これらの両方の組み合わせを実行することもできます。