[理工][資結] Find(x) with path compression

[terry8575 (豪哥)]

https://i.imgur.com/uSOm39h.jpg
想請教一下各位大神們
為什麼最後的時間複雜度是O(log* n)呢？
然後又能看成是O(1)！
一般來說這種時間複雜度都是怎麼判斷的呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.61.220 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1589107923.A.777.html
推 cossetannie: log*n極小 所以可以看成常數
→ terry8575: 懂了！  那O(log* n)這是如何算出來的呀？
推 chengaryguan: http://www.gabrielnivasch.org/fun/inverse-ackerm
→ chengaryguan: ann
→ chengaryguan: 可以參考這個，需要解Ackermann的反函數的遞迴式
→ chengaryguan: http://www.gabrielnivasch.org/fun/inverse-ackerm
→ chengaryguan: ann
→ chengaryguan: 抱歉，網址一直被切斷，總之是找Ackermann的反函數
→ chengaryguan: 的推倒過程。
推 asuku: 幫樓上縮網址https://reurl.cc/X6ADee
太感謝樓上的a大跟c大了！
※ 編輯: terry8575 (49.216.61.220 臺灣), 05/13/2020 16:21:45