Re: [理工] [DS]97交大
※ 引述《xygod (XY)》之銘言：
: 我想問第四題的第2小題
: 題目:http://www2.lib.nctu.edu.tw/n_exam/exam97/cslz/cslz1001.pdf
: 剛剛爬文看到這題是F，原因是建heap只要O(n)
: 可是建heap的時候不是把input 放到 array後，
: 在跑n/2次的adjust，得到一個max(or min)heap
: 這樣子建heap不是應該O(nlgn)嗎??
: 不知道我觀念哪裡錯，麻煩各位救救我~~~
build_max_heap
lgn n
Σ -------- * O(h) // O(h) = O(lgn) 因為每次調整頂多是樹高
h=0 2^(h+1)
lgn h
O( n * Σ ------- )
h=0 2^(h)
之後cormen好像套用什麼公式 得到
O(2n) => O(n)
印象中好像在heapsort那一章@.@
好久沒翻了...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.33.156
※ 編輯: mqazz1 來自: 140.118.33.156 (02/14 17:08)
推
02/14 17:08, , 1F
02/14 17:08, 1F
→
02/14 17:09, , 2F
02/14 17:09, 2F
→
02/14 17:15, , 3F
02/14 17:15, 3F
→
02/14 21:28, , 4F
02/14 21:28, 4F
→
02/14 22:24, , 5F
02/14 22:24, 5F
→
02/14 22:54, , 6F
02/14 22:54, 6F
→
02/14 23:06, , 7F
02/14 23:06, 7F
→
02/14 23:06, , 8F
02/14 23:06, 8F
→
02/14 23:07, , 9F
02/14 23:07, 9F
討論串 (同標題文章)