クイックユニオンの時間複雑度はどのくらいですか？

Question

私はデータ構造とアルゴリズムについてコースラコースを受講しています。著者は、N個のオブジェクトに対するN個の結合演算がN * N個の配列へのアクセスを必要とすることがあるとすれば、O（N^2）が意味を成すクイックファインドを意味すると述べている。しかし、私はなぜクイックユニオンがどんなに良くなるのか分かりません。最悪の場合、1つの細長いツリー、N個のオブジェクトに対するN個の検索操作はO（N^2）にもつながりますが、そのデータはO（N）と言います。

したがって、1つは2次の時間であり、1つは線形です。なぜ違いがあるのか​​分かりません。

Answer 1

// Naive implementation of find 
int find(int parent[], int i) 
{ 
    if (parent[i] == -1) 
     return i; 
    return find(parent, parent[i]); 
} 

// Naive implementation of union() 
void Union(int parent[], int x, int y) 
{ 
    int xset = find(parent, x); 
    int yset = find(parent, y); 
    parent[xset] = yset; 
} 

上記union()とfind()はナイーブであり、最悪の場合の時間複雑度は線形です。サブセットを表現するために作成されたツリーは歪んでいる可能性があり、リンクされたリストのようになります。以下は、最悪のシナリオの例です。

Let there be 4 elements 0, 1, 2, 3 

Initially all elements are single element subsets. 
0 1 2 3 

Do Union(0, 1) 
    1 2 3 
/
0 

Do Union(1, 2) 
    2 3 
    /
    1 
/
0 

Do Union(2, 3) 
     3  
     /
     2 
    /
    1 
/
0 

上記の操作は最悪の場合O(Log n)に最適化できます。アイデアは、より深いツリーのルートの下に常に小さな深さのツリーを付けることです。この技術は、ユニオンbyランクと呼ばれています。ランクという用語は高さの代わりに優先されます。これは、パス圧縮手法（以下で説明しました）を使用すると、ランクが常に高さに等しいとは限りません。

Let us see the above example with union by rank 
Initially all elements are single element subsets. 
0 1 2 3 

Do Union(0, 1) 
    1 2 3 
/
0 

Do Union(1, 2) 
    1 3 
/\ 
0 2 

Do Union(2, 3) 
    1  
/| \ 
0 2 3 

素朴なメソッドの2番目の最適化は、パス圧縮です。考え方は、find()が呼び出されたときにツリーを平坦にすることです。要素xに対してfind()が呼び出されると、ツリーのルートが返されます。 find()オペレーションは、xからトラップしてルートを検索します。パス圧縮の考え方は、発見されたルートを親としてxにすることで、すべての中間ノードを再びトラバースする必要がなくなります。 xがサブツリーのルートである場合、xの下のすべてのノードからのパス（ルートへ）も圧縮されます。

Let the subset {0, 1, .. 9} be represented as below and find() is called 
for element 3. 
       9 
     / | \ 
     4  5  6 
    / \  /\ 
    0  3  7 8 
      /\ 
      1 2 

When find() is called for 3, we traverse up and find 9 as representative 
of this subset. With path compression, we also make 3 as child of 9 so 
that when find() is called next time for 1, 2 or 3, the path to root is 
reduced. 

       9 
     //\ \ 
     4 5 6  3 
    /  /\ /\ 
    0   7 8 1 2   

2つの手法が互いに補完します。各操作の時間複雑度は、O(logn)〜O(n)よりもさらに小さくなります。実際、償却された時間の複雑さは効果的に小さくなります。

上記の最適化でコードを投稿していないのは、私が推測する割り当て部分だからです。それが役に立てば幸い！