[理工] 資結-樹

[taitin (小南)]

兩個問題

第一個問題：

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
推 magic704226:第1題,build把數字都放入array,還沒heapify,所以O(n)
→ magic704226:第2題是7次嘛,iterative mergesort!
推 uminchu185:第1題, 你的想法是採top-down建立, 如果採bottom-up
→ uminchu185:建立, 約有一半的nodes是leaves不用調整, cost是O(n)沒
→ uminchu185:錯, 有興趣可以參考CORMEN 2版p.135