[理工] 105台大資演

[w181496 (Kaibro)]

http://i.imgur.com/8QCSECO.jpg
想請教大神各位幾題

2.c
這題應該怎麼去分析呢？
情感上會直接想寫O(n^3)
補習班答案也給這個

3.a的ii.
這題很不確定
我的想法是
每層hash table都花O(1)時間
所以就求最多幾層能放完
我的答案O(log_m(n))
補習班給的答案是O(n/m^2)

3.b
這題的pairwise collisions是啥意思？
看不懂題目意思GG

感謝各位

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.86.242
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1481947408.A.F63.html
→ ken52011219: https://goo.gl/Gix9re
→ ken52011219: O(n/m) * O(1/m)
→ ken52011219: 通常HASH會將 n = O(m) 因此α = n/m = O(m)/m=O(1)
→ ken52011219: 但這題有提n&m 就要寫清楚 第一層search =O(n/m)
→ ken52011219: 第二層 search =O(1/m)
這邊我不太懂QQ 某個值做hash查詢時不是丟到hash function算位址O(1) 然後O(1)直接
對應到該table中的entry嗎？ 這樣跟m,n應該沒啥關係吧(?
→ ken52011219: 第三題不清楚,是m=n嗎@@?O(n^2)=O(m+n)
→ ken52011219: O(n/n) = O(1)
→ ken52011219: 不確定
這題我第一個直覺也是m=n
但補習班給的答案是m=kn下去算
所以這題題意是要把m當作O(n)嗎(?
※ 編輯: w181496 (39.9.86.242), 12/17/2016 13:28:14
推 aa06697: 2-c.  http://i.imgur.com/z10Ktco.jpg
→ w181496: 話說想一想2.c他說M獨立於n 是不是複雜度寫O(n^3)也沒錯
→ w181496: 阿？
→ yupog2003: 如果M獨立於n可以當常數的話這題直接帶Master Theorem
→ yupog2003: 答案就出來了，不知道可不可以
→ aa06697: 個人覺得他有說是variable而不是constant 所以不能
→ aa06697: 可以想像成T不只有n還有M 是有兩個variable這樣應該就能
→ aa06697: 理解了
→ aa06697: 當然如果考場突然算不出來我也會寫n^3 就看台大老師要不
→ aa06697: 要給分了
→ ken52011219: https://goo.gl/IB7fyG 參考看看
→ ken52011219: 另外 2.C 我覺得不行, O(n^3/m^1/2)⊆O(n^3)
→ ken52011219: 但反之不然
→ ken52011219: 第三題也也不確定 @@~ 第一次看到這個名詞
→ yupog2003: 也就是說保險起見都寫最精確的那個答案就對了，了解
結果聽說補習班老師第二題答案後來改log_m(n)....@@
※ 編輯: w181496 (110.30.225.54), 12/20/2016 16:02:43
→ ken52011219: 居然@@ 所以是大大的講法嗎
不過不一定保證這就是正解啦@@
如果有人有其他想法歡迎一起討論
※ 編輯: w181496 (39.8.2.141), 12/21/2016 17:24:09
推 yupog2003: 也許用decision tree下去想，有m個slot就當作每層有m個
→ yupog2003: 選擇，所以degree為m，有n個element所以leaf數為n
→ yupog2003: 高度log_m(n)，我承認我也是看到答案之後才反推的XD