6

セットAがセットBのサブセットであるかどうかを確認するアルゴリズム(できれば一定時間)はありますか?

この問題を容易にするためにデータ構造を作成しても、実行時間にはカウントされません。

4

3 に答える 3

1

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

ハッシュテーブルを使用すると、O(A+B)アルゴリズムは簡単です ( の要素をハッシュテーブルに格納Bし、 の各要素を検索しますA)。の高度な構造を知らない限り、これ以上のことはできないと思いますB。たとえば、Bがソート順に格納されている場合、O(A log B)二分探索を使用できます。

于 2012-10-05T23:50:27.110 に答える
0

文字列セットに最も一般的でない文字と文字のペアのリストがある場合は、最も一般的でない文字と文字のペアで並べ替えられたセットを保存し、否定的な一致をできるだけ早く捨てる可能性を最大限に高めることができます。これがブルームフィルターとどの程度うまく組み合わされるかは私には明らかではありません.ディグラムや文字があまりないので、おそらくハッシュテーブルでうまくいくでしょう.

サブセットの最大サイズまたは一般的なサイズに関する情報があれば、前述のように、特定のサイズのすべてのサブセットをブルーム フィルターに入れることで、同様にデータを前処理できます。

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

于 2012-10-06T01:28:10.967 に答える
0

ブルーム フィルターを使用することもできます (http://en.wikipedia.org/wiki/Bloom_filter )。ただし、誤検知が発生する可能性があります。これは、上記の Keith が述べた方法で対処できます (ただし、ハッシュの最悪の場合の複雑さは O(n) ではありませんが、O(nlogn) を実行できることに注意してください)。

  1. ブルーム フィルターに従って、A が B のサブセットであるかどうかを確認する
  2. はいの場合は、徹底的なチェックを行います
于 2012-10-06T00:01:52.050 に答える