Re: [理工] [軟設]-中正資工考古\

看板Grad-ProbAsk作者rnbjacky (浪漫A大調)時間14年前 (2011/03/08 01:34)推噓2(2推 0噓 4→)

留言6則, 3人參與討論串3/3 (看更多)

6.(T/F)The worst case time complexity of Dijstra's shortest path algorithm is O(n^3) 我猜 false 講義上只有寫 Dijkstra's Algo Time Complexity 是 O(n^2) 所以我也不清楚 worst case下 time complexity 長怎樣@@" 以Cormen書上的pseudo code來說(一般來說也是) Dijkstra's algo可以分成兩個部分： 1.初始化各點資訊( 含最短距離及老爸 ) => "Build" 一個資料結構 2.While loop 含以下兩個動作 : (1)取出d值最小的點(i.e.取最近的點) =>"ExtractMin" (|V|次) (2)Relax (i.e.改變最短距離的值) =>"DecreasingKey" (至多|E|次) 以Array實作(i.e.Adjacency matrix): 1.Build : Ｏ(V) 2.ExtractMin : Ｏ(V) (需Search整個list) 需|V|次 3.DecreasingKey : Ｏ(1) 　至多需|E|次 TOTAL: Ｏ(V) + Ｏ(V˙V) + Ｏ(E˙1) =Ｏ(V^2) 以Adjacency List搭配BinaryHeap實作 : 1.Build : Ｏ(V) 2.ExtractMin : Ｏ(logV) 需|V|次 3.DecreasingKey : Ｏ(logV) 至多需|E|次 TOTAL: Ｏ(V) + Ｏ(VlogV) + Ｏ(ElogV) =Ｏ(VlogV + ElogV) ( 若要背的話, 背這個 , 不要背Ｏ(ElogV)簡化過的 ) 以Adjacency List搭配FibonacciHeap實作 : 1.Build : Ｏ(V) 2.ExtractMin : Ｏ(logV) 需|V|次 3.DecreasingKey : Ｏ(1) (這個時間非常漂亮!) 至多需|E|次 TOTAL: Ｏ(V) + Ｏ(VlogV) + Ｏ(E˙1) =Ｏ(VlogV + E) (100交大考這個！) 觀察可以發現建立資料結構 (i.e.初始化)　所需時間皆是由頂點數決定但最後會被WHILE LOOP內的時間dominate 而不同的實作方式　可以得到不一樣的時間分析中正這題要考的應該是array的分析 (因為只有出現n) 不然就三種方式都成立了畢竟O(n^3) 不是這麼tightly 後兩者是很重要的分析(而且很美啊！) 如果可以就記一下吧！希望有幫上您的忙！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 221.120.64.23

推

wadekobe324

03/08 01:48, , 1^F

03/08 01:48, 1^F

※ 編輯: rnbjacky 來自: 221.120.64.23 (03/08 01:55)

推

privatewind

03/08 07:45, , 2^F

03/08 07:45, 2^F

→

privatewind

03/08 07:45, , 3^F