[理工] 102成大 演算法

[TampaBayRays (光芒今年拿冠軍)]

https://i.imgur.com/X1fX8Fv.jpg

https://i.imgur.com/nazeQcY.jpg

https://i.imgur.com/iYt4keJ.jpg

請問這題要怎麼推？

雖然已經知道答案可是推到一半就卡住

還是假裝畫一下然後直接猜再證明就好？

感謝～
-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.19.12
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512547659.A.858.html
推 gary70812: http://i.imgur.com/KITILgN.jpg
→ gary70812: 給你參考不確定可不可以這樣寫
→ TampaBayRays: 好像不錯，可是這樣解感覺畫那棵樹是多餘的XD
推 gary70812: 話說你的樹好像有畫錯？每層的值應該不一樣
→ TampaBayRays: 兩個1/2成本不會變吧？
→ TampaBayRays: 應該是你變數代換了所以不一樣
推 gary70812: 例如第二層的分母不是log(n/2)嗎
→ TampaBayRays: 喔喔喔！我好像眼殘了...
→ TampaBayRays: 難怪算不出來....
→ TampaBayRays: 感謝你！我算出來了
推 kyle5408: 請問最後一層n/(2^k(lgn-k)）要如何計算k呢
→ TampaBayRays: 我是令T(2)=c
→ TampaBayRays: K=lgn-1