多重集合のマージの高速化テクニック
- サイズ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に注目すると、高々 回しか小さい方にならない
- 議論:
