作者taitin (小南)
看板Grad-ProbAsk
标题[理工] 资结-树
时间Mon Dec 7 17:07:51 2009
两个问题
第一个问题：
n个数值，min-heap的built time
想法：每次插入是logn 共有n个数字 所以 sum(log n) n from 1~n
= log1+log2+log3+...+logn=log n!<log n^n =nlogn
=>O(nlogn) 但是答案是O(n) why?
第二个问题：
external sort,merging runs to establish asorting sequence:
Given 8 runs in sorted sequence according the files size,
1k 2k 3k 4k 5k 6k 7k 8k
(c) The optimal cost(number of comparisons) to this case.
想法：依照huffman algo.
每次挑两个最小的相加放回，因为已经是sort好的
所以直接挑前面两个
step0. (1,2,3,4,5,6,7,8)
step1. insert 1+2 in sequence
(3,3,4,5,6,7,8) comparison 1 time
step2 insert 3+3 in sequence
(4,5,6,6,7,8) comparison 3 times
step3 insert 4+5 in sequence
(6,6,7,8,9) comparison 4 times
step4 insert 6+6 in sequence
(7,8,9,12) comparison 3 times
step5 insert 7+8 in sequence
(9,12,15) comparison 2 times
step6 insert 9+12 in sequence
(15,21) comparison 1 time
step7 sequence emmpty
total time 1+3+4+3+2+1=14
但答案错了，why?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.7.249
1F：推 magic704226:第1题,build把数字都放入array,还没heapify,所以O(n) 12/07 17:33
2F：→ magic704226:第2题是7次嘛,iterative mergesort! 12/07 17:36
3F：推 uminchu185:第1题, 你的想法是采top-down建立, 如果采bottom-up 12/07 20:12
4F：→ uminchu185:建立, 约有一半的nodes是leaves不用调整, cost是O(n)没 12/07 20:14
5F：→ uminchu185:错, 有兴趣可以参考CORMEN 2版p.135 12/07 20:16