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
感謝各位

https://goo.gl/Gix9reO(n/m) * O(1/m)通常HASH會將 n = O(m) 因此α = n/m = O(m)/m=O(1)但這題有提n&m 就要寫清楚 第一層search =O(n/m)第二層 search =O(1/m)第三題不清楚,是m=n嗎@@?O(n^2)=O(m+n)O(n/n) = O(1)不確定

2-c. http://i.imgur.com/z10Ktco.jpg

話說想一想2.c他說M獨立於n 是不是複雜度寫O(n^3)也沒錯阿？

如果M獨立於n可以當常數的話這題直接帶Master Theorem答案就出來了，不知道可不可以

個人覺得他有說是variable而不是constant 所以不能可以想像成T不只有n還有M 是有兩個variable這樣應該就能理解了當然如果考場突然算不出來我也會寫n^3 就看台大老師要不要給分了

https://goo.gl/IB7fyG 參考看看另外 2.C 我覺得不行, O(n^3/m^1/2)⊆O(n^3)但反之不然第三題也也不確定 @@~ 第一次看到這個名詞

也就是說保險起見都寫最精確的那個答案就對了，了解

居然@@ 所以是大大的講法嗎

也許用decision tree下去想，有m個slot就當作每層有m個選擇，所以degree為m，有n個element所以leaf數為n高度log_m(n)，我承認我也是看到答案之後才反推的XD