1. PTT
  2. Grad-ProbAsk

[理工][資結] 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
繼續閱讀
[理工] 線代ch4解答問題chengaryguan線性代數 4-2tiahi5914[理工] greedy 舉反例tank123zzz[理工] linked list 製作 stack AGENTofAQUA[理工] 離散lanlansaysay線性代數 線性映射tiahi5914[理工] K 在BST中的範圍AGENTofAQUAUnique BTAGENTofAQUA[理工] 資料結構BSTAGENTofAQUA[理工] 離散 非對稱性＆反對稱性frpsjack

Links booklink

Contact Us: admin [ a t ] ucptt.com