小さい方から大きい方へ移す
多重集合のマージの高速化テクニック
サイズXのものをサイズYのものにマージする時にO(X)掛かるとする
pythonfor x in X:
Y.add(x)サイズNの集合の要素を、それぞれの要素だけを持ったサイズ1の集合のマージを繰り返す
素朴に考えるとO(N)のマージをN-1回行うのでO(N^2)
小さい方を大きい方にマージすることにすると、これがO(NlogN)になる
議論:
小さい方をXとする
マージのたびに集合のサイズは2X以上になる
なのである要素xに注目すると、高々\log_2 N 回しか小さい方にならない
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]