[理工] 演算法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
好的我再想想看，感謝你！