[理工] 105台大資工資演

[argorok (chichi111)]

http://imgur.com/a/pjoyK
想問一下
3.a(ii)
這題問題是說另一個H'用來處理H中collison的
因為是uniform，所以每格有n/m筆Data。
H'也是uniform 所以在H'中每格應該有N/M^2筆
在這樣遞迴下去 所以應該是O(logm n)的時間找的到
不知道這樣想法有沒有誤解題目的意思？
3.b 不太了解題目的意思，有人可以幫忙解釋一下嗎?

感謝各位~~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.89.132
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486296779.A.993.html
※ 編輯: argorok (140.113.89.132), 02/05/2017 20:28:51
→ ken52011219:  http://i.imgur.com/tVlomdS.jpg  我後來是這麼想
→ ken52011219: 的
→ ken52011219: 改一下 http://i.imgur.com/IhUvD9O.jpg
※ 編輯: argorok (140.113.89.132), 02/05/2017 21:03:12
※ 編輯: argorok (140.113.89.132), 02/05/2017 21:05:08
→ ken52011219: 有辦法確認一定是一半嗎@@?
→ argorok: 我想錯了@@ 我思考一下
被pairwise collision搞混，所以只要每個slot n/m個是常數k，m=n/k
這樣就可以reduce到O(1)
※ 編輯: argorok (140.113.89.132), 02/05/2017 21:09:50
→ ken52011219: 我的想法來源是從amortized 的stack push & pop
→ ken52011219: 我是這麼想的 但不太常用amortized 不知道有沒有盲點
→ argorok: 如果是這樣應該還要加上增長之後的空間搬移O(n)?
→ argorok: 在分攤掉還是O(1)就是了
※ 編輯: argorok (140.113.89.132), 02/05/2017 21:16:40
→ ken52011219: 恩.. 我剛剛也在考慮這點 但你說的應該沒錯
→ Gabino: 感覺expected number of pairwise collision 跟105交大的h
→ Gabino: ash第二小題 好像是在講一樣的東西 如果用1/(1-n/m)解釋
→ Gabino: 的話 應該就是m=O(n)