[理工] [資結]-樹
兩個問題
第一個問題：
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
推
12/07 17:33, , 1F
12/07 17:33, 1F
→
12/07 17:36, , 2F
12/07 17:36, 2F
推
12/07 20:12, , 3F
12/07 20:12, 3F
→
12/07 20:14, , 4F
12/07 20:14, 4F
→
12/07 20:16, , 5F
12/07 20:16, 5F