[理工] 算法4-47
楼主: z000000000 2020-08-29 22:09:37
想请教这题几个问题
1.用array存取是因为题目给了weight的range 吗？
2.那用array存取，在Prim's 的算法下时间复杂度不是O(V^2)吗，为什么是O(VlogV+E)呢？
3.题目中第2个问号中的range为1到constant W第1个问号为1到|V|，|V|为什么不能视为constant来看呢？(如果能视为constant，时间复杂度2题应该都是O(E)吗)
这题想了很久还是想不清楚，谢谢大家的帮忙！
作者: A4P8T6X9 (残废的名侦探) 2020-08-30 08:24:00
排序 VlogV，使用 union amd find 对每个边找是否形成循环，每个边测试一次，所以是 E。V 不能视为常数的原因是因为点数跟图的大小有关，而 w跟图的大小无关。
楼主: z000000000 2020-08-30 22:41:00
好的我再想想看，感谢你！