小さい方から大きい方へ移す

多重集合のマージの高速化テクニック

• サイズXのものをサイズYのものにマージする時にO(X)掛かるとする python

for x in X:
    Y.add(x)

• サイズNの集合の要素を、それぞれの要素だけを持ったサイズ1の集合のマージを繰り返す

  • 素朴に考えるとO(N)のマージをN-1回行うのでO(N^2)
  • 

• 小さい方を大きい方にマージすることにすると、これがO(NlogN)になる

  • 議論:
    • 小さい方をXとする
    • マージのたびに集合のサイズは2X以上になる
    • なのである要素xに注目すると、高々$\log_2 N$ 回しか小さい方にならない
    •