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

看板Grad-ProbAsk作者 (豪哥)時間4年前 (2020/05/10 18:52), 4年前編輯推噓3(3推 0噓 7→)
留言10則, 4人參與, 4年前最新討論串1/1
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
推
05/10 20:48, 4年前 , 1F
log*n極小 所以可以看成常數
05/10 20:48, 1F
→
05/10 22:41, 4年前 , 2F
懂了！ 那O(log* n)這是如何算出來的呀？
05/10 22:41, 2F
推
05/11 00:53, 4年前 , 3F
05/11 00:53, 3F
→
05/11 00:53, 4年前 , 4F
ann
05/11 00:53, 4F
→
05/11 00:53, 4年前 , 5F
可以參考這個，需要解Ackermann的反函數的遞迴式
05/11 00:53, 5F
→
05/11 00:54, 4年前 , 6F
05/11 00:54, 6F
→
05/11 00:54, 4年前 , 7F
ann
05/11 00:54, 7F
→
05/11 00:57, 4年前 , 8F
抱歉，網址一直被切斷，總之是找Ackermann的反函數
05/11 00:57, 8F
→
05/11 00:57, 4年前 , 9F
的推倒過程。
05/11 00:57, 9F
推
05/11 16:01, 4年前 , 10F
幫樓上縮網址https://reurl.cc/X6ADee
05/11 16:01, 10F
太感謝樓上的a大跟c大了！ ※ 編輯: terry8575 (49.216.61.220 臺灣), 05/13/2020 16:21:45
‣ 更多 terry8575 的文章
文章代碼(AID): #1UjzpJTt (Grad-ProbAsk)