好奇两种算法的优劣

Louis_lxy @ 2024-05-27 19:51:03

by lunjiahao @ 2024-05-27 20:26:20

@lunjiahao

哦哦，忘说了 Prim 是要加堆优化才有 O(n \log n) 的

by zjh114514 @ 2024-05-27 20:32:07

@ldh270657080 kruskal 直接存边就行吧

by yinianxingkong @ 2024-05-27 20:35:28

@lunjiahao 如果是二叉堆或者优先队列 Prim 复杂度是 O((n+m) \log n) 吧。

要 O(n \log n+m) 得斐波那契堆。

by yinianxingkong @ 2024-05-27 20:37:21

似乎优先队列优化的复杂度和 kruskal 一样是 O(m \log m)。

by Louis_lxy @ 2024-05-27 21:09:05

感觉理论上 kruskal 是会比 prim 慢一点，因为很多数据都是 m>n。

by Louis_lxy @ 2024-05-27 21:11:09

@Igallta 为啥你的记录无论是那个算法都比我的慢很多啊？感觉是你写法有问题。

by Igallta @ 2024-05-27 21:11:45

@ldh270657080

对的，因为您是大佬，您最强了。

by dctc800d @ 2024-05-27 21:11:57

@ldh270657080 优化后都是 m \log m！！！

而且你怎么推出 Kruskal 是 m \log n 的，它是对边排序啊。。。

by Louis_lxy @ 2024-05-27 21:13:43

@dctc800d 算错了

by Louis_lxy @ 2024-05-27 21:14:14

@dctc800d 是 prim 不是 kruskal 啊