[理工][资结] Find(x) with path compression

楼主: terry8575 (豪哥)   2020-05-10 18:52:01
https://i.imgur.com/uSOm39h.jpg
想请教一下各位大神们
为什么最后的时间复杂度是O(log* n)呢?
然后又能看成是O(1)!
一般来说这种时间复杂度都是怎么判断的呢?
作者: cossetannie (paa)   2020-05-10 20:48:00
log*n极小 所以可以看成常数
楼主: terry8575 (豪哥)   2020-05-10 22:41:00
懂了! 那O(log* n)这是如何算出来的呀?
作者: chengaryguan (garychen)   2020-05-11 00:53:00
http://www.gabrielnivasch.org/fun/inverse-ackermann可以参考这个,需要解Ackermann的反函数的递回式http://www.gabrielnivasch.org/fun/inverse-ackermann抱歉,网址一直被切断,总之是找Ackermann的反函数的推倒过程。
作者: asuku (すく)   2020-05-11 16:01:00
帮楼上缩网址https://reurl.cc/X6ADee

Links booklink

Contact Us: admin [ a t ] ucptt.com