發現版上好像沒有參考答案想說和大家對答案看看 > <
題目: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)
有錯誤的地方再麻煩大家指正惹> <
謝謝大家~

我也有寫答案跟你的都一樣 不過資結第二題我的答案是(n-u)/(n*m^u)但是我覺得我應該是錯的@@

想問B.2是怎麼算的順便請問5是怎麼算的QQ感謝!

想問資結第一題的第一小題為什麼是True呢？open addressing 的comparison次數是 1/alpha x ln(1/1-alpha) ，alpha是load factor 。這樣的話如果load factor接近1 ，comparison 次數不就會變得比O(n)大很多嗎（假設n是已經存入hash table的element次數）