2006年11月04日
union/find の
- 2006-11-04 (Sat)
- 一般
経路圧縮とランクによる合併操作をあわせる，n 要素で操作回数が m 回のときに O(m a(m,n)) とのことだが，何で Ackermann 関数の逆関数 a(m,n) （正確な逆関数では無いらしいが…）が登場するのだろう？ O(m lg*(n)) の評価は原理が簡単だが a(m,n) の方は面倒らしい．機会があれば調べてみるか．どっちにしろ無視できるスピードの関数だからどうでもいいのだけど．
- Comments: 0
- TrackBack (Close): -