完全图上跑prim再用堆优化会是逆优化吗?
查看原帖
完全图上跑prim再用堆优化会是逆优化吗?
376467
QDHSLGYYJK楼主2021/3/24 20:44

据说prim复杂度是O(N2)O(N^2),然而可以用堆优化优化到O((N+M)logN)O((N+M)logN) ,然而例如这题是完全图,MM 就跟 N2N^2 一个数量级了,感觉就会多了一个 O(logN)O(logN) 的数量级反而会多耗时,不太懂这些求教wq

2021/3/24 20:44
加载中...