マージテク (大きいサイズに小さいサイズをマージする)
概要
複数のグループに分かれたデータをクエリに従ってマージ (片方のグループの要素をもう片方のグループに加える) することを何も工夫せずに実行すると、
- サイズ 1 のグループにサイズ 10 のグループをマージする。(要素移動が 10 = 計算量 10)
- サイズ 11 のグループにサイズ 10000 のグループをマージする。(計算量 10000)
のようになり、最悪計算量が \(O(N^2)\) になる。
そこで「サイズが大きいグループに小さいグループをマージする」ように改良すると (クエリと大小が異なる場合は swap する)、ならし計算量が \(O(N\log{N})\) になる。
Union Find の高速化でも同様な手法が用いられる。
計算量
計算量は各要素ごとに着目すると簡単に理解できる。
マージテクを利用したマージを行うことを考える。この時、ある要素がマージによってグループ移動した場合、マージ後グループのサイズは元々所属していたグループのサイズの 2 倍以上になる。
したがって全体のサイズが \(N\) の時、着目した要素がグループ移動するのは高々 \(\log{N}\) 回しかない。
つまり全体での計算量は \(N\log{N}\) になる。