[理工] [資結]union-and-find

[c5onb (大邱)]

想請問一下

u unions and f finds

到底可不可以在Θ(f+u)做完呢？



我用的是Horowitz的課本

裡面提到最快的方法是用wighted + collapsed

但是複雜度要用一個奇怪的α-function來算

雖然成長很緩慢  但是應該也不是linear的

想問問大家的想法？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 123.110.136.216
推 richard730:可以喔! 那個叫做 Ackerman的反函數 趨近於O(1)
推 kiwidoit:你u個unions用weighting rule所需時間O(u) 而做出來的
→ kiwidoit:set每個element做find都O(1)阿，做u次只要O(u)
→ kiwidoit:忘了講..要依序坐union
→ kiwidoit:如果沒依序作union的話find最差要O(logu)，所以再用
→ kiwidoit:collapsing rule做find的話就可以保證下一輪的find只要
→ kiwidoit:O(1)就能完成