http://i.imgur.com/8QCSECO.jpg
想请教大神各位几题
2.c
这题应该怎么去分析呢？
情感上会直接想写O(n^3)
补习班答案也给这个
3.a的ii.
这题很不确定
我的想法是
每层hash table都花O(1)时间
所以就求最多几层能放完
我的答案O(log_m(n))
补习班给的答案是O(n/m^2)
3.b
这题的pairwise collisions是啥意思？
看不懂题目意思GG
感谢各位

https://goo.gl/Gix9reO(n/m) * O(1/m)通常HASH会将 n = O(m) 因此α = n/m = O(m)/m=O(1)但这题有提n&m 就要写清楚 第一层search =O(n/m)第二层 search =O(1/m)第三题不清楚,是m=n吗@@?O(n^2)=O(m+n)O(n/n) = O(1)不确定

2-c. http://i.imgur.com/z10Ktco.jpg

话说想一想2.c他说M独立于n 是不是复杂度写O(n^3)也没错阿？

如果M独立于n可以当常数的话这题直接带Master Theorem答案就出来了，不知道可不可以

个人觉得他有说是variable而不是constant 所以不能可以想像成T不只有n还有M 是有两个variable这样应该就能理解了当然如果考场突然算不出来我也会写n^3 就看台大老师要不要给分了

https://goo.gl/IB7fyG 参考看看另外 2.C 我觉得不行, O(n^3/m^1/2)⊆O(n^3)但反之不然第三题也也不确定 @@~ 第一次看到这个名词

也就是说保险起见都写最精确的那个答案就对了，了解

居然@@ 所以是大大的讲法吗

也许用decision tree下去想，有m个slot就当作每层有m个选择，所以degree为m，有n个element所以leaf数为n高度log_m(n)，我承认我也是看到答案之后才反推的XD