[理工] 104 台大資演

看板Grad-ProbAsk作者 (YO)時間9年前 (2015/02/09 21:12), 9年前編輯推噓4(4推 0噓 10→)
留言14則, 7人參與, 最新討論串1/2 (看更多)
倒數第二題，問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
→
02/09 21:35, , 1F
(1) V^3 (2) V^1.5logV (3) V^1.5
02/09 21:35, 1F
推
02/09 21:37, , 2F
其實這題問的是worst case
02/09 21:37, 2F
感謝 已補
推
02/09 21:42, , 3F
(1) O(V^2) (2) V^1.5logV (3) V^1.5
02/09 21:42, 3F
※ 編輯: mkchiun1028 (211.23.164.210), 02/09/2015 21:44:07
→
02/09 21:43, , 4F
worst沒錯吧!?
02/09 21:43, 4F
→
02/09 21:44, , 5F
第一個 decress key 我是想成O(1) extract_min想成O(V)
02/09 21:44, 5F
→
02/09 21:46, , 6F
第一個沒有提供data structure應該在adj list找?
02/09 21:46, 6F
→
02/09 21:48, , 7F
我也是想adjacency list找 找min應該是O(V^1.5)?
02/09 21:48, 7F
→
02/09 21:49, , 8F
第一題我寫V^3.5 想說找min edge V^1.5, 比對有無cyc
02/09 21:49, 8F
→
02/09 21:50, , 9F
le V^1, 重複做V次,總共V^3.5 只是很寬鬆就是了...
02/09 21:50, 9F
→
02/09 22:01, , 10F
我是想第一個點找min V 第二個點 2V 要做到V-1個點
02/09 22:01, 10F
→
02/09 22:02, , 11F
V+2V+...+(V-1)V=O(V^3)
02/09 22:02, 11F
推
02/09 23:27, , 12F
找 min 不能用 binary search嗎?
02/09 23:27, 12F
→
02/09 23:42, , 13F
題目說用greedy找
02/09 23:42, 13F
推
02/10 00:05, , 14F
(2) 使用loser tree，leaf是cost最小 請問為何是O(V^1.5log
02/10 00:05, 14F
‣ 更多 mkchiun1028 的文章
文章代碼(AID): #1KsB96np (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 mkchiun1028 的文章
文章代碼(AID): #1KsB96np (Grad-ProbAsk)