[理工] 資演 成大109 資料結構第二題+對答案

看板Grad-ProbAsk作者 (貓貓只求黑琴ㄍㄟˋ婚 )時間5年前 (2020/12/17 21:38), 5年前編輯推噓2(2推 0噓 9→)
留言11則, 3人參與, 5年前最新討論串1/1
發現版上好像沒有參考答案想說和大家對答案看看 > < 題目: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://www.ptt.cc/bbs/Grad-ProbAsk/M.1608212284.A.1F8.html ※ 編輯: try66889 (114.32.191.76 臺灣), 12/17/2020 21:42:47
推
12/17 22:30, 5年前 , 1F
我也有寫答案跟你的都一樣 不過資結第二題我的答案是(n
12/17 22:30, 1F
→
12/17 22:30, 5年前 , 2F
-u)/(n*m^u)
12/17 22:30, 2F
→
12/17 22:31, 5年前 , 3F
但是我覺得我應該是錯的@@
12/17 22:31, 3F
感謝j大 OWO 方便請問j大資結第二題是怎麼考慮的嗎 > <? 想說聽聽看大家的想法 > < ※ 編輯: try66889 (114.32.191.76 臺灣), 12/17/2020 23:30:47
→
12/18 01:21, 5年前 , 4F
想問B.2是怎麼算的
12/18 01:21, 4F
→
12/18 01:23, 5年前 , 5F
順便請問5是怎麼算的QQ
12/18 01:23, 5F
第二題我是這樣做～ https://i.imgur.com/tePGKIs.jpg
第五題～ https://i.imgur.com/klUzXiW.jpg
※ 編輯: try66889 (114.32.191.76 臺灣), 12/18/2020 01:48:44
→
12/18 02:28, 5年前 , 6F
感謝!
12/18 02:28, 6F
推
12/18 07:43, 5年前 , 7F
想問資結第一題的第一小題為什麼是True呢？open add
12/18 07:43, 7F
→
12/18 07:43, 5年前 , 8F
ressing 的comparison次數是 1/alpha x ln(1/1-alph
12/18 07:43, 8F
→
12/18 07:43, 5年前 , 9F
a) ，alpha是load factor 。這樣的話如果load facto
12/18 07:43, 9F
→
12/18 07:43, 5年前 , 10F
r接近1 ，comparison 次數不就會變得比O(n)大很多嗎
12/18 07:43, 10F
→
12/18 07:43, 5年前 , 11F
（假設n是已經存入hash table的element次數）
12/18 07:43, 11F
不過全部insert的Data是n個，最壞應該就把每個Data search一次~ ※ 編輯: try66889 (114.32.191.76 臺灣), 12/18/2020 10:35:48
‣ 更多 try66889 的文章
文章代碼(AID): #1Vsryy7u (Grad-ProbAsk)