作者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