作者terry8575 (豪哥)
看板Grad-ProbAsk
標題[理工][資結] Find(x) with path compression
時間Sun May 10 18:52:01 2020
https://i.imgur.com/uSOm39h.jpg
想請教一下各位大神們
為什麼最後的時間複雜度是O(log* n)呢？
然後又能看成是O(1)！
一般來說這種時間複雜度都是怎麼判斷的呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.61.220 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1589107923.A.777.html
1F：推 cossetannie: log*n極小 所以可以看成常數05/10 20:48
2F：→ terry8575: 懂了！ 那O(log* n)這是如何算出來的呀？05/10 22:41
4F：→ chengaryguan: ann05/11 00:53
5F：→ chengaryguan: 可以參考這個，需要解Ackermann的反函數的遞迴式05/11 00:53
7F：→ chengaryguan: ann05/11 00:54
8F：→ chengaryguan: 抱歉，網址一直被切斷，總之是找Ackermann的反函數05/11 00:57
9F：→ chengaryguan: 的推倒過程。05/11 00:57
太感謝樓上的a大跟c大了！
※ 編輯: terry8575 (49.216.61.220 臺灣), 05/13/2020 16:21:45