[理工]成大105程設 演算法

看板Grad-ProbAsk作者 (馬吉叫我辦的)時間9年前 (2017/01/10 09:27), 編輯推噓10(10推 0噓 9→)
留言19則, 7人參與, 最新討論串1/1
跟大家對一下4 5 6題的答案 然後第7題不會寫 順便問一下第5題有更快的方法嗎? 因為六個矩陣相乘的計算量很多 還有第6題的nlgn+c直接變theta(nlgn)這樣可以嗎? 還是要多寫些什麼? 麻煩大家了!! http://i.imgur.com/GRKjgUp.jpg
http://i.imgur.com/9rZyrjp.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 182.235.130.102 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484011645.A.613.html
推
01/10 10:03, , 1F
4,5,6都跟你一樣 第5題應該是沒有更快的方法了
01/10 10:03, 1F
→
01/10 10:04, , 2F
第7題一樣卡位等高手
01/10 10:04, 2F
推
01/10 10:18, , 3F
第五題這種DP就只能硬幹了，15分值得啦
01/10 10:18, 3F
→
01/10 10:19, , 4F
第6題我後面會寫log(n)+log(n-1)+log(n-2)欸，雖然答案
01/10 10:19, 4F
→
01/10 10:19, , 5F
會是一樣
01/10 10:19, 5F
推
01/10 10:23, , 6F
第七題我是這樣想，因為n個變數相加除以n會大於等於n個
01/10 10:23, 6F
→
01/10 10:23, , 7F
變數相乘開n次根號（這叫什麼定理我也忘了），所以我們
01/10 10:23, 7F
→
01/10 10:24, , 8F
要找相乘之後最大的結果，等於是找相加後最小的結果，所
01/10 10:24, 8F
→
01/10 10:24, , 9F
以這個問題其實是找u,v兩點之間的shortest path
01/10 10:24, 9F
→
01/10 10:24, , 10F
n個變數就是u到v之間會經過的每個點的r值，例如u-x-y-v
01/10 10:24, 10F
→
01/10 10:25, , 11F
就有3個變數r(u,x),r(x,y),r(y,v)
01/10 10:25, 11F
推
01/10 10:32, , 12F
第六題你的推論不嚴謹吧 你要先證O 然後證Ω 才能得到Θ
01/10 10:32, 12F
→
01/10 10:34, , 13F
第七題是把所有 weight 改成倒數取 log 就可以用最短路徑
01/10 10:34, 13F
推
01/10 10:37, , 14F
第六題那樣的出法也要夾擊嗎
01/10 10:37, 14F
推
01/10 10:52, , 15F
不是說要 asymptotically tight 嗎?
01/10 10:52, 15F
推
01/12 18:57, , 16F
第5題的時間複雜度是theta(n^3) 算很久...難怪一格一分
01/12 18:57, 16F
推
01/24 01:10, , 17F
第六題可以寫根據master theorem嗎
01/24 01:10, 17F
推
01/24 01:12, , 18F
第七題 FRAXIS大 我一直在想怎麼相乘 忘了還有log
01/24 01:12, 18F
推
01/17 17:37, , 19F
第五題/5，最後再乘5^3
01/17 17:37, 19F
‣ 更多 h9638512 的文章
文章代碼(AID): #1OT3XzOJ (Grad-ProbAsk)