发现版上好像没有参考答案想说和大家对答案看看 > <
题目: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次数）