[理工] 105 台大資工 資演

看板Grad-ProbAsk作者 (chichi111)時間8年前 (2017/02/05 20:12), 8年前編輯推噓0(0推 0噓 13→)
留言13則, 3人參與, 最新討論串1/4 (看更多)
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
→
02/05 20:52, , 1F
我後來是這麼想
02/05 20:52, 1F
→
02/05 20:52, , 2F
的
02/05 20:52, 2F
→
02/05 20:56, , 3F
02/05 20:56, 3F
※ 編輯: argorok (140.113.89.132), 02/05/2017 21:03:12 ※ 編輯: argorok (140.113.89.132), 02/05/2017 21:05:08
→
02/05 21:05, , 4F
有辦法確認一定是一半嗎@@?
02/05 21:05, 4F
→
02/05 21:06, , 5F
我想錯了@@ 我思考一下
02/05 21:06, 5F
被pairwise collision搞混，所以只要每個slot n/m個是常數k，m=n/k 這樣就可以reduce到O(1) ※ 編輯: argorok (140.113.89.132), 02/05/2017 21:09:50
→
02/05 21:06, , 6F
我的想法來源是從amortized 的stack push & pop
02/05 21:06, 6F
→
02/05 21:12, , 7F
我是這麼想的 但不太常用amortized 不知道有沒有盲點
02/05 21:12, 7F
→
02/05 21:14, , 8F
如果是這樣應該還要加上增長之後的空間搬移O(n)?
02/05 21:14, 8F
→
02/05 21:14, , 9F
在分攤掉還是O(1)就是了
02/05 21:14, 9F
※ 編輯: argorok (140.113.89.132), 02/05/2017 21:16:40
→
02/05 21:17, , 10F
恩.. 我剛剛也在考慮這點 但你說的應該沒錯
02/05 21:17, 10F
→
02/05 22:01, , 11F
感覺expected number of pairwise collision 跟105交大的h
02/05 22:01, 11F
→
02/05 22:01, , 12F
ash第二小題 好像是在講一樣的東西 如果用1/(1-n/m)解釋
02/05 22:01, 12F
→
02/05 22:01, , 13F
的話 應該就是m=O(n)
02/05 22:01, 13F
‣ 更多 argorok 的文章
文章代碼(AID): #1ObnRBcJ (Grad-ProbAsk)
‣ 更多 argorok 的文章
文章代碼(AID): #1ObnRBcJ (Grad-ProbAsk)