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

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

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

code:python

for x in X:

Y.add(x)

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

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

https://gyazo.com/5b592048a795de209b82cc446fbfd768

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

議論:

小さい方をXとする

マージのたびに集合のサイズは2X以上になる

https://gyazo.com/82116cda69fb4047b785b3d8f7154fb1