[理工] 105台大資演

看板Grad-ProbAsk作者 (Kaibro)時間9年前 (2016/12/17 12:03), 9年前編輯推噓2(2推 0噓 25→)
留言27則, 4人參與, 最新討論串1/1
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
→
12/17 12:07, , 1F
12/17 12:07, 1F
→
12/17 12:37, , 2F
O(n/m) * O(1/m)
12/17 12:37, 2F
→
12/17 12:39, , 3F
通常HASH會將 n = O(m) 因此α = n/m = O(m)/m=O(1)
12/17 12:39, 3F
→
12/17 12:40, , 4F
但這題有提n&m 就要寫清楚 第一層search =O(n/m)
12/17 12:40, 4F
→
12/17 12:40, , 5F
第二層 search =O(1/m)
12/17 12:40, 5F
這邊我不太懂QQ 某個值做hash查詢時不是丟到hash function算位址O(1) 然後O(1)直接 對應到該table中的entry嗎？ 這樣跟m,n應該沒啥關係吧(?
→
12/17 12:56, , 6F
第三題不清楚,是m=n嗎@@?O(n^2)=O(m+n)
12/17 12:56, 6F
→
12/17 12:57, , 7F
O(n/n) = O(1)
12/17 12:57, 7F
→
12/17 12:57, , 8F
不確定
12/17 12:57, 8F
這題我第一個直覺也是m=n 但補習班給的答案是m=kn下去算 所以這題題意是要把m當作O(n)嗎(? ※ 編輯: w181496 (39.9.86.242), 12/17/2016 13:28:14
推
12/17 13:41, , 9F
12/17 13:41, 9F
→
12/17 13:48, , 10F
話說想一想2.c他說M獨立於n 是不是複雜度寫O(n^3)也沒錯
12/17 13:48, 10F
→
12/17 13:48, , 11F
阿？
12/17 13:48, 11F
→
12/17 13:52, , 12F
如果M獨立於n可以當常數的話這題直接帶Master Theorem
12/17 13:52, 12F
→
12/17 13:53, , 13F
答案就出來了，不知道可不可以
12/17 13:53, 13F
→
12/17 14:01, , 14F
個人覺得他有說是variable而不是constant 所以不能
12/17 14:01, 14F
→
12/17 14:02, , 15F
可以想像成T不只有n還有M 是有兩個variable這樣應該就能
12/17 14:02, 15F
→
12/17 14:02, , 16F
理解了
12/17 14:02, 16F
→
12/17 14:04, , 17F
當然如果考場突然算不出來我也會寫n^3 就看台大老師要不
12/17 14:04, 17F
→
12/17 14:04, , 18F
要給分了
12/17 14:04, 18F
→
12/17 14:54, , 19F
12/17 14:54, 19F
→
12/17 14:57, , 20F
另外 2.C 我覺得不行, O(n^3/m^1/2)⊆O(n^3)
12/17 14:57, 20F
→
12/17 14:57, , 21F
但反之不然
12/17 14:57, 21F
→
12/17 15:14, , 22F
第三題也也不確定 @@~ 第一次看到這個名詞
12/17 15:14, 22F
→
12/17 17:45, , 23F
也就是說保險起見都寫最精確的那個答案就對了，了解
12/17 17:45, 23F
結果聽說補習班老師第二題答案後來改log_m(n)....@@ ※ 編輯: w181496 (110.30.225.54), 12/20/2016 16:02:43
→
12/20 16:45, , 24F
居然@@ 所以是大大的講法嗎
12/20 16:45, 24F
不過不一定保證這就是正解啦@@ 如果有人有其他想法歡迎一起討論 ※ 編輯: w181496 (39.8.2.141), 12/21/2016 17:24:09
推
12/22 07:10, , 25F
也許用decision tree下去想，有m個slot就當作每層有m個
12/22 07:10, 25F
→
12/22 07:10, , 26F
選擇，所以degree為m，有n個element所以leaf數為n
12/22 07:10, 26F
→
12/22 07:11, , 27F
高度log_m(n)，我承認我也是看到答案之後才反推的XD
12/22 07:11, 27F
‣ 更多 w181496 的文章
文章代碼(AID): #1OLBaGzZ (Grad-ProbAsk)