→ cksh8008:拜託幫忙.. 02/09 20:27
http://0rz.tw/RqzWg
http://0rz.tw/aVJEZ 好讀版
想請問第五、七大題
五.
(a)F
為O(n);
(b)F
O(n)的時間內可達成
(c)T
只須執行4*(n+r)次就可以完成-> O(n)
(d)T
因不可紅點連續，故最長為紅黑紅黑
又因黑點數須相同，所以2a>=B
(e)F(不確定)
不存在
雖Insert和Delete可達O(1)
但因為是Dynamic,member需要O(n)的時間
(f)F
O(n)的時間內可達成
第七大題不會，但還是寫寫看了，錯了希望高手能解釋為什麼
七.
(a)
沒有方法，
因要計算最短路徑，每點每邊都須走過一次
因dijkstra alog每次都可確認一點故最多執行O(n-2)次
又dijkstra algo每次僅計算該點的相鄰邊->O(m)
故為O(mn)
Bellman須O(n^3) Foyld-Warshall須O(n^3)
(b1) O(mlogn)
(b2) O(m+vlogv)
(b3) O(n^2)
(b4) O(n^2+nlogn)
(這四題其實不會，只是把adjancent List和matrix的時間複雜度寫下來
然後直覺把min-heap當成F-heap寫而已)
拜託各位高手指教了，謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 175.181.103.2
※ 編輯: cksh8008 來自: 175.181.103.2 (02/08 16:01)
※ 編輯: cksh8008 來自: 175.181.103.2 (02/08 16:02)