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

[rnbjacky (浪漫A大調)]

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:謝謝講解~~~
※ 編輯: rnbjacky        來自: 221.120.64.23        (03/08 01:55)
推 privatewind:交大的資結一向是背多分 0.0+ 不然就考生天生神力，
→ privatewind:當場推出來
→ rnbjacky:第三個當場推的出來我就要跪了...= =
→ privatewind:要全推 很難啦 有一些基礎去推 還ok 當然了，你要有
→ privatewind:過人的勇氣跟他賭 你推的是否正確