[理工] 105台大資工資演 sdfg014025xx PTT批踢踢實業坊

作者: sdfg014025xx (隨便就好) 2019-02-10 00:24:04

https://i.imgur.com/RgkWy1C.jpg
爬文後的答案好像是
a小題 O(log(n/m))
b小題 O(m)=n
兩題都不是很懂，請問有人知道嗎？
感謝

作者: anonimo (unknown) 2019-02-10 01:56:00

b小題這個廣為流傳的答案應該是錯的我覺得是m=n^2詳細可以看CLRS p.279

作者: plsmaop (plsmaop) 2019-02-10 07:55:00

台大喜歡從clrs裡直接出幾題

作者: CorkiN (柯基) 2019-02-10 09:39:00

第一題第一小題O(1*logn)第一題第二小題O(1*1)第一小題log裡面是n/m，前面打錯抱歉><

作者: leviliang (levi) 2019-02-10 21:28:00

https://i.imgur.com/CZxUww2.jpg(b)小題m=O(N)喔，蔡欣穆教授的投影片有證

作者: anonimo (unknown) 2019-02-11 00:09:00

蔡欣穆投影片和這個講的是不同東西吧一個是在說search是constant time 這題題目是在問兩兩碰撞次數的期望值https://imgur.com/oAsVsTS

作者: leviliang (levi) 2019-02-11 07:28:00

阿謝謝a大 a大的解答才是對的！樓主可以把a大的解答框起來，以前的討論全錯了XD

作者: GeniusPuddin (GeniusPudding) 2019-02-14 16:12:00

推上面的定理

繼續閱讀