[解決済み] n個のユニオンのfind（サイズによるユニオン）演算を実行する際の時間計算量がO(n log n)であるのはなぜか？

疑問点

ユニオン検索操作のツリーベースの実装では、各要素はノードに格納され、そのノードにはセット名へのポインタが含まれます。セットポインタがvを指すノードvもまた、セット名である。各セットは、自己参照セットポインタを持つノードをルートとするツリーである。

結合を行うには、一方の木の根を他方の木の根に一致させればよい。検索を行うには、開始ノードからセット名ポインタをたどって、セット名ポインタが自分自身を参照するノードに到達するまでの間、検索を行う。

サイズ別ユニオンの場合 -> ユニオンを実行する場合、小さい方のツリーの根を が大きい方の根を指す。このことから、O(n log n)時間 n回のunion find操作を行う。ポインタをたどるたびに、前のサブツリーの最大2倍の大きさのサブツリーに行くことになる。従って、どの検索でも最大O(log n)個のポインタをたどることになる。

各単一化操作に対して、Find操作が常にO(log n)であることが理解できないのですが。どなたか、最悪の場合の複雑さが実際にどのように計算されるのか、説明していただけませんか？

どのように解決するのですか？

とりあえず、高さhの各木は少なくとも2^hのノードを含むと仮定してみよう。このような木を2つ連結するとどうなるでしょうか？

サイズが異なる場合、結合された木の高さは高い方の木の高さと同じになるので、新しい木は依然として2^h以上のノードを持ちます（高さは同じですがノードの数が増えます）。

さて、もし同じ高さであれば、出来上がった木は高さが1つ増え、少なくとも2^h + 2^h = 2^(h+1)のノードを含むことになります。つまり、この条件はまだ成立します。

最も基本的な木（1ノード、高さ0）でも条件を満たす。したがって、2本の木をつなげて作ることができる木はすべてこの条件を満たすことになる。

さて、高さとは、単に検索時にたどるステップの最大数である。木がn個のノードと高さh（n >= 2^h）を持つ場合、これは直ちにlog2(n) >= h >=ステップを与えます。