作者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/cn.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