有名な素集合データ構造について読んでいたところ、「素集合データ構造か素集合データ構造のどちらかがO(n)
時間がかかり、もう一方が時間がかかるO(1)
」と書かれていました。
しかし、セットを表すためにビット文字列を使用するのはどうですか?次に、union(ビットORを使用)とfind(セットリストを繰り返して対応するビットがであるかどうかを確認する)の両方1
がかかりO(1)
ます。
そのロジックの何が問題になっていますか?
有名な素集合データ構造について読んでいたところ、「素集合データ構造か素集合データ構造のどちらかがO(n)
時間がかかり、もう一方が時間がかかるO(1)
」と書かれていました。
しかし、セットを表すためにビット文字列を使用するのはどうですか?次に、union(ビットORを使用)とfind(セットリストを繰り返して対応するビットがであるかどうかを確認する)の両方1
がかかりO(1)
ます。
そのロジックの何が問題になっていますか?
O(Alpha(n))
両方の操作は、Alphaが(非常にゆっくりとinverse of the Ackermann function
成長する)の償却時間で実行できます。あなたは問題を森として表現しなければなりません。いくつかのサブグラフ(ツリーノード)の代表を選択すると、ユニオン操作によってツリーがマージされます(小さいツリーを高い方のルートの下にぶら下げます)。和集合演算は、単純にルートまでトラバースし、トラバースされたパスを短縮します(検索された要素(場合によってはすべてのトラバースされた要素)をルートの下にぶら下げます)。
ビットフィールド付き
or
が、nが大きい場合は、明らかに組み込み型を使用できません。また、ビットフィールドは任意のセットにはあまり適していません。たとえば、任意の32ビット整数を含むことができるセットがある場合、4G / 8=0.5Gのサイズのビットフィールドが必要です。