作者assassin88 (AI)
看板Grad-ProbAsk
标题[理工] [DS]-资料结构演算法几个小问题
时间Tue Dec 29 15:07:00 2009
一、写题目碰到"Loading density"是指？
洪逸跟解答定义不同，解答是写n/t(这是洪逸定义的identifier density)，
洪逸定义为n/b*s，他应该是照恐龙翻的，所以是解答写错吗？
注：n为identifier使用个数，t为hash table所有的identifier个数，
b为bucket个数，s为bucket中slot个数。
可是这样照字面意思，又好像解答是对的= ="
二、Merging two AVL trees of n-node each can be done in O(n) time in the worst
case？
不知道答案为何，不过感觉是false，觉得是O(nlogn)..不知道对吗？
三、关於hashing的题目，如果没注明n次overflow(指：超过他给定的f(x)都还是溢位)，
接着该怎麽安插位置？是直接作linear probing吗？
问题有点多..请多指教~~~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 编辑: assassin88 来自: 140.135.167.46 (12/29 15:08)
1F：推 FRAXIS:第二题 先把两个tree转成ordered array 12/29 16:58
2F：→ FRAXIS:然後merge成一个新的ordered array 12/29 16:58
3F：→ FRAXIS:再从新的ordered array 建立一个平衡的二元树即可 12/29 16:59
4F：→ assassin88:按照你的说法那应该是nlogn没错~感谢 12/29 17:02
5F：→ FRAXIS:按照我的说法应该是 O(n).. 12/29 17:11
6F：→ assassin88:先转两个tree不就是O(n)，再建立AVL~O(logn)？ 12/29 17:22
7F：推 FRAXIS:建立应该只要O(n) 递回去建.. 12/29 20:51
8F：→ assassin88:回家看了答案..是false耶XD 12/29 22:40