[理工] 105台大資工 資演

看板Grad-ProbAsk作者 (隨便就好)時間6年前 (2019/02/10 00:24), 編輯推噓8(8推 0噓 7→)
留言15則, 5人參與, 6年前最新討論串2/2 (看更多)
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
推
02/10 01:56, 6年前 , 1F
b小題這個廣為流傳的答案應該是錯的 我覺得是m=n^2
02/10 01:56, 1F
→
02/10 01:57, 6年前 , 2F
詳細可以看CLRS p.279
02/10 01:57, 2F
推
02/10 07:55, 6年前 , 3F
台大喜歡從clrs裡直接出幾題
02/10 07:55, 3F
推
02/10 09:39, 6年前 , 4F
第一題第一小題O(1*logn)
02/10 09:39, 4F
→
02/10 09:39, 6年前 , 5F
第一題第二小題O(1*1)
02/10 09:39, 5F
推
02/10 09:46, 6年前 , 6F
第一小題log裡面是n/m，前面打錯抱歉><
02/10 09:46, 6F
推
02/10 21:28, 6年前 , 7F
02/10 21:28, 7F
→
02/10 21:32, 6年前 , 8F
(b)小題m=O(N)喔，蔡欣穆教授的投影片有證
02/10 21:32, 8F
推
02/11 00:09, 6年前 , 9F
蔡欣穆投影片和這個講的是不同東西吧 一個是在說
02/11 00:09, 9F
→
02/11 00:10, 6年前 , 10F
search是constant time 這題題目是在問兩兩碰撞次數的
02/11 00:10, 10F
→
02/11 00:11, 6年前 , 11F
期望值
02/11 00:11, 11F
→
02/11 00:14, 6年前 , 12F
02/11 00:14, 12F
推
02/11 07:28, 6年前 , 13F
阿 謝謝a大 a大的解答才是對的！
02/11 07:28, 13F
→
02/11 07:30, 6年前 , 14F
樓主可以把a大的解答框起來，以前的討論全錯了XD
02/11 07:30, 14F
推
02/14 16:12, 6年前 , 15F
推上面的定理
02/14 16:12, 15F
‣ 更多 sdfg014025xx 的文章
文章代碼(AID): #1SNlwdIZ (Grad-ProbAsk)
‣ 更多 sdfg014025xx 的文章
文章代碼(AID): #1SNlwdIZ (Grad-ProbAsk)