[理工] 102成大演算法 TampaBayRays PTT批踢踢實業坊

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-06 16:07:33

https://i.imgur.com/X1fX8Fv.jpg
https://i.imgur.com/nazeQcY.jpg
https://i.imgur.com/iYt4keJ.jpg
請問這題要怎麼推？
雖然已經知道答案可是推到一半就卡住
還是假裝畫一下然後直接猜再證明就好？
感謝～

作者: gary70812 (1) 2017-12-06 16:30:00

http://i.imgur.com/KITILgN.jpg給你參考不確定可不可以這樣寫

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-06 16:37:00

好像不錯，可是這樣解感覺畫那棵樹是多餘的XD

作者: gary70812 (1) 2017-12-06 16:41:00

話說你的樹好像有畫錯？每層的值應該不一樣

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-06 16:46:00

兩個1/2成本不會變吧？應該是你變數代換了所以不一樣

作者: gary70812 (1) 2017-12-06 16:48:00

例如第二層的分母不是log(n/2)嗎

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-06 16:50:00

喔喔喔！我好像眼殘了...難怪算不出來....感謝你！我算出來了

作者: kyle5408 (SmAcKeR) 2017-12-06 18:47:00

請問最後一層n/(2^k(lgn-k)）要如何計算k呢

作者: TampaBayRays (光芒今年拿冠軍) 2017-12-06 20:37:00

我是令T(2)=cK=lgn-1

繼續閱讀