19

ウィキペディアの素集合フォレストの和集合/検索アルゴリズムの内訳は次のとおりです。

  • ばらばらなばらばらの森... ( O(n))
    • ... ランクごとに結合 ... (現在は に改善O(log(n))
      • ...パス圧縮あり（現在O(a(n))、効果的に に改善されていますO(1)）

ランクによる結合を実装するには、各ノードがrank比較のためにフィールドを保持する必要があります。私の質問は、ランクによる結合はこの追加スペースの価値があるかということです? ランクによる結合をスキップして、代わりにパス圧縮を行うとどうなりますか? それは十分ですか？現在の償却複雑度は?

O(log(n)パス圧縮 (償却された複雑さ) のないランクによる結合は、ほとんどの実用的なアプリケーションに十分であることを意味するコメントが作成されます。正解です。私が求めているのは逆です: ランクによるユニオンをスキップして、代わりにパス圧縮のみを行うとどうなりますか?

ある意味で、パスの圧縮は、ランクごとの結合を改善するための追加の手順であり、そのため、その追加の手順を省略しても悲惨な結果を招くことはありません。しかし、ランクによる結合はパス圧縮に必要な中間ステップですか? それをスキップして直接パス圧縮に進むことはできますか?

また、ランクによる結合がなければ、結合が繰り返されると連結リストのような構造が作成される可能性があることも指摘されました。これは、単一パスの圧縮操作がO(n)最悪の場合にかかる可能性があることを意味します。もちろん、これは将来の運用に影響を与えるため、多くの運用で償却したときにこれがどのように機能するかが、私がより興味を持っていることです.

4

2 に答える 2

7

「ランクごとの組合なし」をグーグルで検索したところ、2番目に表示されたリンクは次のとおりです。

...このセクションは、パス圧縮を使用するがランクによる結合を使用しないユニオン検索の分析で締めくくります...

パス圧縮を使用するがランクによる結合を使用しないユニオン検索データ構造は、時間 O((m+n) log n) で m 個の検索および n-1 回のリンク操作を処理します。

于 2010-02-24T14:29:30.810 に答える
3

パス圧縮により、ツリー構造が平坦化されます。ランクごとのユニオンはマージに役立ちます。後者をスキップするとします。これで、マージ方法を選択するためのランク情報を持たないフォレストができました。潜在的に、深さの大きいツリーを深さの小さいツリーにマージするリスクがあり、ツリー構造のバランスが崩れる可能性があります。最悪の場合、連結リストになってしまうこともあります。ユニオンの償却時間の複雑さは、検索のそれが同じままであっても増加します。

IMO、ランクではなくパス圧縮をスキップする方が良いでしょう。

于 2010-02-24T03:12:05.837 に答える