[理工] 108交大資演 11

看板Grad-ProbAsk作者 (野格炸彈)時間5年前 (2020/01/30 12:48), 編輯推噓2(202)
留言4則, 2人參與, 5年前最新討論串1/1
http://i.imgur.com/seUdA9O.jpg
http://i.imgur.com/uuUzxGv.jpg
第23題 解答只有D 這題我是用類似matrix chain 的DP做的 但是這樣應該是O(n^3) 這題有n^2內的做法ㄇ ----- Sent from JPTT on my Sony H9493. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.14.137.229 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580359729.A.777.html

01/30 12:53, 5年前 , 1F
你沒辦法證明他的下界 可能存在 只是沒人想到
01/30 12:53, 1F

01/30 13:21, 5年前 , 2F
就是在有跟沒有之間 沒找到而已
01/30 13:21, 2F

01/31 12:01, 5年前 , 3F
matrix chain 有 O(n lg n) 法
01/31 12:01, 3F

01/31 12:09, 5年前 , 4F
這題我猜滿足 quadrangle inequality 所以可以 O(n^2)
01/31 12:09, 4F
文章代碼(AID): #1UCc0nTt (Grad-ProbAsk)