1

有名な素集合データ構造について読んでいたところ、「素集合データ構造か素集合データ構造のどちらかがO(n)時間がかかり、もう一方が時間がかかるO(1)」と書かれていました。

しかし、セットを表すためにビット文字列を使用するのはどうですか？次に、union（ビットORを使用）とfind（セットリストを繰り返して対応するビットがであるかどうかを確認する）の両方1がかかりO(1)ます。

そのロジックの何が問題になっていますか？

4

2 に答える 2

6

O(Alpha(n))両方の操作は、Alphaが（非常にゆっくりとinverse of the Ackermann function成長する）の償却時間で実行できます。あなたは問題を森として表現しなければなりません。いくつかのサブグラフ（ツリーノード）の代表を選択すると、ユニオン操作によってツリーがマージされます（小さいツリーを高い方のルートの下にぶら下げます）。和集合演算は、単純にルートまでトラバースし、トラバースされたパスを短縮します（検索された要素（場合によってはすべてのトラバースされた要素）をルートの下にぶら下げます）。

于 2011-10-12T15:02:53.023 に答える
3

ビットフィールド付き

  • 和集合はO（n）になります。2つのネイティブ整数に対して単純なビットを実行できると想定しますorが、nが大きい場合は、明らかに組み込み型を使用できません。
  • 発見はO（1）になります。繰り返す必要はありません。ビットの正確な位置がわかります。

また、ビットフィールドは任意のセットにはあまり適していません。たとえば、任意の32ビット整数を含むことができるセットがある場合、4G / 8=0.5Gのサイズのビットフィールドが必要です。

于 2011-10-12T09:20:19.897 に答える