Hot_tear @ 2024-02-17 10:59:56
为什么这个题按秩合并我跑了 2.33s(最大点770+ms) 路径压缩只有 165ms 理论上来说不应该是差不多的，为什么会差那么多呢？
by BPG_ning @ 2024-02-17 11:09:44
事实上路径压缩比按秩合并快得多，按秩合并是log，路径压缩是反阿克曼函数，可以看成常数级别
by BPG_ning @ 2024-02-17 11:12:00
@Hot_tear 而且您写的好像是启发式合并，而且写错了
by angiing1222 @ 2024-02-17 11:16:13
不懂就问，启发式合并与按秩合并之间有什么不同吗
by Hot_tear @ 2024-02-17 11:16:58
@BPG_ning 中间70分时脑子突然抽了，非常感谢您的回复！QWQ
by BPG_ning @ 2024-02-17 11:17:20
@angiing1222 挺不同的，按秩合并是按树高合并，启发式合并是按树的大小合并
by Hot_tear @ 2024-02-17 11:17:30
@angiing1222 诶，对啊
by BPG_ning @ 2024-02-17 11:17:53
@Hot_tear qwq
by angiing1222 @ 2024-02-17 11:18:41
@BPG_ning 。。。原来如此
我一直以为这两个东西是同一个
by angiing1222 @ 2024-02-17 11:19:22
但是单路径压缩也能被卡到log级别
by Hot_tear @ 2024-02-17 11:19:32
@BPG_ning 但是不应该是路径压缩+按秩合并才是反阿克曼函数吗？单这两个中任意一个都应该是log啊？