作者try66889 (貓貓只求黑琴ㄍㄟˋ婚 )
看板Grad-ProbAsk
標題[理工] 資演 成大109 資料結構第二題+對答案
時間Thu Dec 17 21:37:57 2020
發現版上好像沒有參考答案想說和大家對答案看看 > <
題目:
https://reurl.cc/OqZDAA
A.資料結構
1.TFFFT
2.這題不知道怎麼做QQ 在想題目的意思是不是在問u個key K
放到m個bucket發生碰撞的機率?
自己是寫1-[m(m-1)(m-2)...(m-u+1)]/m^u
不過不是很有信心...QQ
3.64
B.演算法
1.TF
2.θ(nloglogn)
3.median-of-medians做
4.<0,1,0,1,0,1>
5.不適用Master Theory，用展開帶入法 θ(n^3˙loglogn)
有錯誤的地方再麻煩大家指正惹> <
謝謝大家~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.191.76 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1608212284.A.1F8.html
※ 編輯: try66889 (114.32.191.76 臺灣), 12/17/2020 21:42:47
1F：推 jay010540: 我也有寫答案跟你的都一樣 不過資結第二題我的答案是(n12/17 22:30
2F：→ jay010540: -u)/(n*m^u)12/17 22:30
3F：→ jay010540: 但是我覺得我應該是錯的@@12/17 22:31
感謝j大 OWO 方便請問j大資結第二題是怎麼考慮的嗎 > <?
想說聽聽看大家的想法 > <
※ 編輯: try66889 (114.32.191.76 臺灣), 12/17/2020 23:30:47
4F：→ mathtsai: 想問B.2是怎麼算的12/18 01:21
5F：→ mathtsai: 順便請問5是怎麼算的QQ12/18 01:23
第二題我是這樣做～
https://i.imgur.com/tePGKIs.jpg
第五題～
https://i.imgur.com/klUzXiW.jpg
※ 編輯: try66889 (114.32.191.76 臺灣), 12/18/2020 01:48:44
6F：→ mathtsai: 感謝! 12/18 02:28
7F：推 jimmylin1024: 想問資結第一題的第一小題為什麼是True呢？open add 12/18 07:43
8F：→ jimmylin1024: ressing 的comparison次數是 1/alpha x ln(1/1-alph 12/18 07:43
9F：→ jimmylin1024: a) ，alpha是load factor 。這樣的話如果load facto 12/18 07:43
10F：→ jimmylin1024: r接近1 ，comparison 次數不就會變得比O(n)大很多嗎 12/18 07:43
11F：→ jimmylin1024: （假設n是已經存入hash table的element次數） 12/18 07:43
不過全部insert的Data是n個，最壞應該就把每個Data search一次~
※ 編輯: try66889 (114.32.191.76 臺灣), 12/18/2020 10:35:48