3

ユニオン/検索構造の「パス圧縮による加重クイックユニオン」アルゴリズムを学習しています。Princeton edu サイトでは、アルゴリズムについて詳しく説明されています。Java での実装は次のとおりです。

public class WQUPC {
  private int[] id;
  private int[] sz;
  public WQUPC(int N) {
    id = new int[N];
    sz = new int[N];
    for (int i = 0; i < N; i++) {
      id[i] = i;
      sz[i] = 1;
    }
  }

  int root(int i) {
    while (i != id[i]) {
      id[i] = id[id[i]];
      i = id[i];
    }
    return i;
  }

  boolean connected(int p, int q) { return root(p) == root(q); }

  void union(int p, int q) {
    int i = root(p);
    int j = root(q);
    if (sz[i] < sz[j]) {
      id[i] = j;
      sz[j] += sz[i];
    } else {
      id[j] = i;
      sz[i] += sz[j];
    }
  }
}

しかし、ウェブサイトがそのパフォーマンスについて言及しているように：

定理: 空のデータ構造から開始すると、N 個のオブジェクトに対する M 個の和集合と検索操作のシーケンスは、O(N + M lg* N) 時間かかります。

• 証明は非常に難しい。

• しかし、アルゴリズムは依然として単純です。

しかし、反復対数 lg*n がどのように得られるかについてはまだ興味があります。それはどのように導出されますか？誰かがそれを証明したり、直感的に説明したりできますか?

4

2 に答える 2

5

まず、あなたの質問にはわずかな間違いがあります。パス圧縮だけの複雑さはO(m log(n)) (反復ログなし) だけです。たとえば、Introduction To Algorithmsの演習 21-4.4 を参照してください。実際、あなたはブロックします

    if (sz[i] < sz[j]) {
      id[i] = j;
      sz[j] += sz[i];
    } else {
      id[j] = i;
      sz[i] += sz[j];
    }

ランクごとに結合します。

ただし、ランクによる結合とパス圧縮の両方を使用すると、使用した式を簡単に証明できます (逆アッカーマン式よりもはるかに簡単です)。証明は、次の 3 点に基づいています。

  1. 各リーフ ルート パスでは、各ノードのランクが増加しています。実際、これはランクごとのユニオンに依存しており、それを使用すると、非常に簡単に表示できます。

  2. ツリーのルートのランクがrの場合、ツリーには少なくとも2 つのrノードがあります。これは誘導によって示すことができます。

2.に基づいて、表示することが可能です

  1. ランクrのノードの最大数は最大でn / 2 rです。

証明の残りの部分は、ランクを編成する可能性のある最悪の方法の巧妙な配置に続いています。詳細については、この に関するウィキペディアのエントリを参照してください。

于 2016-09-02T13:19:01.947 に答える
1

私が思い出したように、証明は一連の検索でパス圧縮のコストを償却することに関係していました。浅い検索は安価であり、多くのパス圧縮のコストが発生しません。深い検索では、その検索とパスの圧縮に多くのコストがかかりますが、パスの圧縮により、後続の検索が平均してはるかに安くなります。

于 2016-09-02T12:49:46.283 に答える