[理工] 資結與algo 102 交大

看板Grad-ProbAsk作者 (Ny)時間10年前 (2014/02/08 21:57), 編輯推噓2(2推 0噓 4→)
留言6則, 5人參與, 最新討論串1/1
資結與演算法第12題 Suppose that all edge weights in a graph G are integers in the range from 1 to |V|. How fast can you make Kruskal's algorithm run? 小弟只知道一般的Kruskal's algorithm的時間複雜度 這題不知道如何下手 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.46.189
→
02/08 22:17, , 1F
其實這題是cormen一模一樣的習題== 在23.2.4答案估夠有
02/08 22:17, 1F
推
02/08 22:24, , 2F
http://ppt.cc/3CXv 投影片第36頁最底下
02/08 22:24, 2F
推
02/08 22:58, , 3F
用counting sort排序邊
02/08 22:58, 3F
→
02/08 23:02, , 4F
感謝 另外請問排序完後 find跟union是做E回合 每次O(1)這樣嗎
02/08 23:02, 4F
→
02/08 23:08, , 5F
yes
02/08 23:08, 5F
→
02/09 12:46, , 6F
所以答案是O(E a(V))嗎？？
02/09 12:46, 6F
‣ 更多 Nysw 的文章
文章代碼(AID): #1IzZUn_l (Grad-ProbAsk)