1. PTT
  2. Grad-ProbAsk

[理工] 108交大資演 11

作者: misaka0120 (野格炸彈)   2020-01-30 12:48:47
http://i.imgur.com/seUdA9O.jpg
http://i.imgur.com/uuUzxGv.jpg
第23題
解答只有D
這題我是用類似matrix chain 的DP做的
但是這樣應該是O(n^3)
這題有n^2內的做法ㄇ
作者: zuchang (chang)   2020-01-30 12:53:00
你沒辦法證明他的下界 可能存在 只是沒人想到就是在有跟沒有之間 沒找到而已
作者: FRAXIS (喔喔)   2020-01-31 12:01:00
matrix chain 有 O(n lg n) 法這題我猜滿足 quadrangle inequality 所以可以 O(n^2)
繼續閱讀
[理工] 交大 108 計系 31, 32jean20157[理工] 中正108 電機計組第7 MIPS轉C++naivelydream[理工] 107台大電機 離散 5stellawang18[理工] 108清大計系leegaga61029[理工] 107交大線代10-3willie7878Re: [理工] 102 台大資工 線代11Moderator[理工] 資結 winner/loser treeok8752665[理工] 作業系統henry970117[理工] 108中央計系6.13.18.19hsiehongRe: [理工] [線代]-對稱矩陣--->可對角化?ponwar87123

Links booklink

Contact Us: admin [ a t ] ucptt.com