作者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/cn.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