[理工] 104 台大資演

[mkchiun1028 (YO)]

倒數第二題，問Prim's演算法worst case的複雜度

點數V, 邊數E=V^1.5

(1) 沒有使用任何data structure

(2) 使用loser tree，leaf是cost最小的邊

(3) 使用Fibonacci Heap

大家這題寫什麼呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 211.23.164.210
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1423487558.A.C73.html
→ galapous: (1) V^3 (2) V^1.5logV (3) V^1.5
推 harryron9: 其實這題問的是worst case
感謝 已補
推 tp6m4xup6: (1) O(V^2)  (2) V^1.5logV  (3) V^1.5
※ 編輯: mkchiun1028 (211.23.164.210), 02/09/2015 21:44:07
→ galapous: worst沒錯吧!?
→ tp6m4xup6: 第一個 decress key 我是想成O(1) extract_min想成O(V)
→ galapous: 第一個沒有提供data structure應該在adj list找?
→ mkchiun1028: 我也是想adjacency list找  找min應該是O(V^1.5)?
→ mkchiun1028: 第一題我寫V^3.5 想說找min edge V^1.5, 比對有無cyc
→ mkchiun1028: le V^1, 重複做V次,總共V^3.5  只是很寬鬆就是了...
→ galapous: 我是想第一個點找min V 第二個點 2V 要做到V-1個點
→ galapous: V+2V+...+(V-1)V=O(V^3)
推 FRAXIS: 找 min 不能用 binary search嗎?
→ abc12321: 題目說用greedy找
推 APE36: (2) 使用loser tree，leaf是cost最小 請問為何是O(V^1.5log