作者sdfg014025xx (隨便就好)
看板Grad-ProbAsk
標題[理工] 105台大資工 資演
時間Sun Feb 10 00:24:04 2019
https://i.imgur.com/RgkWy1C.jpg
爬文後的答案好像是
a小題 O(log(n/m))
b小題 O(m)=n
兩題都不是很懂，請問有人知道嗎？
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.50.138.157
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549729447.A.4A3.html
1F：推 anonimo: b小題這個廣為流傳的答案應該是錯的 我覺得是m=n^2 02/10 01:56
2F：→ anonimo: 詳細可以看CLRS p.279 02/10 01:57
3F：推 plsmaop: 台大喜歡從clrs裡直接出幾題 02/10 07:55
4F：推 CorkiN: 第一題第一小題O(1*logn) 02/10 09:39
5F：→ CorkiN: 第一題第二小題O(1*1) 02/10 09:39
6F：推 CorkiN: 第一小題log裡面是n/m，前面打錯抱歉>< 02/10 09:46
8F：→ leviliang: (b)小題m=O(N)喔，蔡欣穆教授的投影片有證 02/10 21:32
9F：推 anonimo: 蔡欣穆投影片和這個講的是不同東西吧 一個是在說 02/11 00:09
10F：→ anonimo: search是constant time 這題題目是在問兩兩碰撞次數的 02/11 00:10
11F：→ anonimo: 期望值 02/11 00:11
13F：推 leviliang: 阿 謝謝a大 a大的解答才是對的！ 02/11 07:28
14F：→ leviliang: 樓主可以把a大的解答框起來，以前的討論全錯了XD 02/11 07:30
15F：推 GeniusPuddin: 推上面的定理 02/14 16:12