[理工]104台大資工 資演對答案

[pups003 (AnAnNiHoa)]

http://i.imgur.com/IBCmRGH.jpg

http://i.imgur.com/Il8IVQy.jpg

第6題我的想法是：
把找出最短距離的時間乘上devide的時間，所以都*logn，還請大神們開示～～

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.72.50
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455287001.A.63B.html
→ pups003:  http://i.imgur.com/bZS3yMB.jpg
→ pups003: 更正一下第五題，但是5（1）有爭議我也不確定
推 FRAXIS: 第六題應該是套 Master theorem 吧
→ pups003: 對齁，我都忘了....感謝f大！
推 iwtes: 借問一下為什麼6.3是O(n^2logn)
推 leoturkey: 第六題要怎麼看啊@@
推 Billgaspeed: 把空間切成兩相等分 T(n) = 2T(n/2) + [看題目給啥]
→ Billgaspeed: 再帶入Master Theorem
推 b0029049:  http://i.imgur.com/hwpuMJa.jpg  第6題應該是這樣吧
→ b0029049: ～
推 leoturkey: 原來如此 感謝
→ nevergrowup: 不確定要寫theta還是bigO 我覺得要寫theta～～
推 Bassy: 推~
推 alan2579: 5(1) 是不是N^2才對啊
推 wooootack: 我也覺得5(1)是O(V^2)，O(E+V^2)
→ wooootack: 如果不用heap的話，decrease key是不是O(1)就可以了