[理工] 演算法4-47
想請教這題幾個問題
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1598710179.A.807.html
推
08/30 08:24,
5年前
, 1F
08/30 08:24, 1F
→
08/30 08:24,
5年前
, 2F
08/30 08:24, 2F
→
08/30 08:26,
5年前
, 3F
08/30 08:26, 3F
→
08/30 08:26,
5年前
, 4F
08/30 08:26, 4F
→
08/30 22:41,
5年前
, 5F
08/30 22:41, 5F