[理工] 105台大資工 資演

[sdfg014025xx (隨便就好)]

https://i.imgur.com/RgkWy1C.jpg
爬文後的答案好像是
a小題 O(log(n/m))
b小題 O(m)=n

兩題都不是很懂，請問有人知道嗎？


感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.138.157
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549729447.A.4A3.html
推 anonimo: b小題這個廣為流傳的答案應該是錯的 我覺得是m=n^2
→ anonimo: 詳細可以看CLRS p.279
推 plsmaop: 台大喜歡從clrs裡直接出幾題
推 CorkiN: 第一題第一小題O(1*logn)
→ CorkiN: 第一題第二小題O(1*1)
推 CorkiN: 第一小題log裡面是n/m，前面打錯抱歉><
推 leviliang: https://i.imgur.com/CZxUww2.jpg
→ leviliang: (b)小題m=O(N)喔，蔡欣穆教授的投影片有證
推 anonimo: 蔡欣穆投影片和這個講的是不同東西吧 一個是在說
→ anonimo: search是constant time 這題題目是在問兩兩碰撞次數的
→ anonimo: 期望值
→ anonimo: https://imgur.com/oAsVsTS
推 leviliang: 阿 謝謝a大 a大的解答才是對的！
→ leviliang: 樓主可以把a大的解答框起來，以前的討論全錯了XD
推 GeniusPuddin: 推上面的定理