作者z000000000 ()
看板Grad-ProbAsk
标题[理工] 演算法4-47
时间Sat Aug 29 22:09:37 2020
http://i.imgur.com/WE7LCy8.jpg
http://i.imgur.com/2QnNfbR.jpg
想请教这题几个问题
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)吗)
这题想了很久还是想不清楚，谢谢大家的帮忙！
-----
Sent from JPTT on my Samsung SM-G885Y.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.137.177.116 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1598710179.A.807.html
1F：推 A4P8T6X9: 排序 VlogV，使用 union amd find 对每个边找是否形成 08/30 08:24
2F：→ A4P8T6X9: 回圈，每个边测试一次，所以是 E。 08/30 08:24
3F：→ A4P8T6X9: V 不能视为常数的原因是因为点数跟图的大小有关，而 w 08/30 08:26
4F：→ A4P8T6X9: 跟图的大小无关。 08/30 08:26
5F：→ z000000000: 好的我再想想看，感谢你！ 08/30 22:41