0

次のデータ構造のうち、挿入、削除、ルックアップ、交差の設定、結合に最も適しているものはどれですか? 時間の複雑さを最適化します。

  1. ビットマップ
  2. 二分探索木
4

1 に答える 1

3

前方

質問があいまいなので、いくつかの仮定を立てます。

最初に、[0 から M] の範囲の一連の数値を表現しようとしています。ここで、M は 100,000 のようなかなり小さい数値です。

BST には、セット内の要素を単純に含めることができます。

Bitmap の長さは M ビットだけで、その位置の数値がセットにある場合はビットが設定され、そうでない場合は数値がセットにありません。サイズ M の Bitmap が既に作成されていると仮定します。

この回答では、セルフバランシング バイナリ サーチ ツリーとビットマップを検討します。非バランシング BST の場合、各操作で最良のケース、平均的なケース、および最悪のケースに対処する必要があります。

操作と複雑さ

挿入: セットに n を追加します。

  • BSTの挿入には O( log(n) ) の時間がかかります。
  • ビットマップでは、ターゲット ビットに対する単純な (OR 1) 操作が必要であり、その 1 を適切な場所に配置するために迅速な除算といくつかのシフトを行う必要がありますが、これは O( 1 ) のままです。

削除: セットから n を削除します。

  • BSTは要素を見つけて削除し、次にツリーを回転させるので、全体として O( log(n) ) になります。
  • ビットマップでは、ターゲット ビットに対する単純な (AND 0) 演算が必要であり、その 1 を適切な場所に配置するために迅速な除算といくつかのシフトを行う必要がありますが、これは O( 1 ) のままです。

ルックアップ: n はセット内にあるか?

  • BSTは O( log(n) ) を使用して n を検索します。
  • ビットマップは、特定のターゲット ビットで (AND 1) の値を返し、除算とシフトを行って 1 を適切な場所に配置します (全体として O( 1 ))。

セットの交点: ここに 2 つのセットがありますが、どちらも同じです。

  • BSTs : 一種の MergeSort スタイルで両方の BST の順序どおりのトラバーサルを行います。2 つの要素が同じである場合は、それを戻り BST に追加します。

    • ソートされた順序で返された BST に要素を追加することはバランスをとるのに悪いため、BST の半分を順番にトラバーサルし、bST の後半を逆順にトラバーサルしてから、交差を追加することでこれを変更できます。 forward-list と reverse-list の要素を交互に並べます。
    • 全体として、これは O( n*log(n) ) のようなものです。戻り BST にすべての要素を追加すると、トラバースよりも時間がかかるためです。

  • Bitmap : 両方のビットマップを走査し、( AND ) バイト (または一度に 32 ビット) を格納し、結果の場所にビットマップとして格納します。O( M ) ここで、M はビットマップが初期化される範囲のサイズです。

Set Union: ここに 2 つのセットがあります。それらを組み合わせます。

  • BSTs : BST1 と BST2 の間で交互に BST1 と BST2 の幅優先トラバーサルを実行することにより、BST1 と BST2 のすべての要素を追加して、新しい BST を作成します。要素が既に存在する場合は、再度追加しないでください。全体として、これは O( n * log(n) ) のようなものです。
  • ビットマップ: 交点の設定と同じですが、( OR ) 演算を使用します。O( M ) ここで、M はビットマップの範囲のサイズです。

質問のあいまいさ

  • これらのセットに格納されるアイテムは何ですか (数値、オブジェクト)
  • 分析対象の二分探索木は自己均衡していますか?
  • これは合理的に小さい有限範囲から選択されたセットですか? (つまり、これはビットマップで実行できますか?)
  • Optimize Time Complexity が何を意味するのかは不明ですが、「このデータ構造に対するこの操作の平均的なケースで知られている Big-O の最小値 (上限) は?」という意味のようです。

結論

ビットマップは、これらのほぼすべての操作について、自己平衡型 BST よりも優れています。

包含/除外ビットマップの欠点:

  • 包含/除外のみを保存し、その要素に関するデータは保存しません。
  • 整数、または 1 対 1 の方法で整数にハッシュされたオブジェクトでのみ機能します (ハッシュ関数が可逆であれば、オブジェクトを元に戻すことができます)。
  • 0 から 100,000 までの整数など、要素の固定範囲が必要です。
  • 固定範囲は、1 億未満など、適度に小さくする必要があります。
  • Union と Intersection は、表現される要素の数ではなく、Range Size に依存します。
于 2012-07-23T08:30:01.630 に答える