路径压缩的均摊时间复杂度为何是O（logｎ）？

boy♂Next♂dooor @ 2024-06-15 12:35:12

by _Yonder_ @ 2024-06-15 12:37:16

因为你不路径压缩，就会访问多次非祖先的点，压缩后每个点就只会被访问接近log次了

by yinianxingkong @ 2024-06-15 12:37:59

@boy♂Next♂dooor 猜你想搜

by _Yonder_ @ 2024-06-15 12:38:25

@Yonder 不过一般都是写作O（α）的，相当于O（1）

by masonxiong @ 2024-06-15 12:40:25

@Yonder

似乎当你同时使用 路径压缩 和 启发式合并 进行优化的时候才是 O(\alpha(n))

单 路径压缩 是 O(\log n)

by yinianxingkong @ 2024-06-15 12:41:50

@Yonder 路径压缩可以卡成 O(\log n)，要按秩合并才是 O(\alpha(n)) 的。

by _Yonder_ @ 2024-06-15 12:42:37

@masonxiong ok谢谢，我没有过多了解过，学了个新知识

by _Yonder_ @ 2024-06-15 12:44:55

@yinianxingkong 谢谢

by boy♂Next♂dooor @ 2024-06-15 15:16:48

@Yonder 我就是想知道为何是logn

by boy♂Next♂dooor @ 2024-06-15 15:18:51

@yinianxingkong 然而我问的是单纯路径压缩的 均摊时间复杂度

by boy♂Next♂dooor @ 2024-06-15 15:21:10

@yinianxingkong 那里面说的是最坏时间复杂度吧