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