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