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

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

by yinianxingkong @ 2024-06-15 16:04:04

@boy♂Next♂dooor

额……

您确定您问的“均摊复杂度”？

我感觉您问的是“平均复杂度”，您可以看作常数，但在 OI 中谈平均没意义，因为都可以卡。

均摊复杂度指的是势能摊到每个操作上的复杂度。刚才给您看的文章讲的就是均摊复杂度上界，也就是最坏均摊复杂度 O(\log n)。

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

@yinianxingkong 虽然我看不太懂那个证明的过程，但是证明一个算法的时间复杂度，怎么会依赖于一个特殊构造的数据呢？

by yinianxingkong @ 2024-06-15 16:47:50

@boy♂Next♂dooor

您没听明白么？一个算法的复杂度要看最坏而不是平均，有数据可以把它卡到最坏它的复杂度就是那个最坏的复杂度，我们复杂度是看上界。

by ylzqwq @ 2024-06-15 16:50:35

@boy♂Next♂dooor 建议重学渐进时间复杂度

by yinianxingkong @ 2024-06-15 16:52:55

@boy♂Next♂dooor 我大概理解了，您是不是不知道上界，而是不理解它为什么上界是那个复杂度是吗？

文章里写的是最坏情况，既然无法更坏那么复杂度就是这样了。

by ylzqwq @ 2024-06-15 16:53:56

@boy♂Next♂dooor O 记号表示一个复杂度的渐近上界

by yinianxingkong @ 2024-06-15 16:54:14

@boy♂Next♂dooor 结合前文的证明再找缺了按秩合并的漏洞应该更好理解一点。

by boy♂Next♂dooor @ 2024-06-15 17:07:06

@yinianxingkong 好吧 谢谢你 虽然那个过程我还是看不懂一点