作者mqazz1 (無法顯示)
看板Grad-ProbAsk
標題Re: [理工] [DS]97交大
時間Mon Feb 14 17:06:53 2011
※ 引述《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)
推 cakeboy:用top down O(nlogn) bottom up O(n) 02/14 17:08
→ cakeboy:請問導公式要背嗎 02/14 17:09
→ xygod:感謝! 02/14 17:15
→ mqazz1:應該是不用背吧 知道建heap是O(n)應該就可了 02/14 21:28
→ ybite:我覺得考了也沒有幾個人會qqqqqqq 02/14 22:24
→ mqazz1:我看cormen把相關的東西都放在習題那一塊...很囧" 02/14 22:54
→ aoqq12:是cormen 的程式不一樣嘛 怎麼會分析到O(n) 02/14 23:06
→ aoqq12:= ="還停留在洪逸解釋的公式 nlogn中 02/14 23:06
→ dy957:其實也不用什麼公式 ..就令為S 然後和2S相減 可得等比 02/14 23:07