[理工] 103 交大資演 pyramidinc PTT批踢踢實業坊

[理工] 103 交大資演

作者: pyramidinc (PyramidInc) 2019-12-21 23:13:21

1.
https://i.imgur.com/CGeSwdZ.jpg
請問兩題怎麼算？第一題我算到
https://i.imgur.com/moLH6U0.jpg
這樣再來就不會了第二題是完全不會算
2.
https://i.imgur.com/vkUULem.jpg
這題答案給的遞迴式是T(n)=2T(n/2)+n
想問一下為什麼是+n 不是+2n ?
兩側都有switch不是嗎？

作者: zuchang (chang) 2019-12-21 23:22:00

二側各2/n第一題最後sigma i4次方就可以直接寫i的五次方了演算法課本有證明

作者: mistel (Mistel) 2019-12-21 23:29:00

https://i.imgur.com/YkDBu8m.jpg下面那題你也可以觀察他的結構只是提供一個完全想不到的時候比較直觀的方法

作者: pyramidinc (PyramidInc) 2019-12-22 00:13:00

感謝我還是不太懂為什麼是兩側各n/2 @@ 圖片中左側不是從1、2、3、4一直寫到n 嗎？

作者: zuchang (chang) 2019-12-22 00:21:00

1.2共用一個所以只需一半

作者: pyramidinc (PyramidInc) 2019-12-22 12:51:00

對耶哈哈感謝

繼續閱讀

[理工] 103中央OS與計組ponwar87123 [理工] 105交大資演 23 quciksortdsa66253 [理工] 計組下冊 p38yoz4ni [理工] 計組 101台聯 pipelined branchching4562 [理工] 103中央數學（離散）ponwar87123 離散zxc2179vbnm [理工] 資結 queue一題ching4562 [理工] 104 交大複雜度一題ching4562 [理工] 離散 1-29 例6jean20157 [理工] 103中央資演以及spooing的意思ponwar87123