[理工] 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

继续阅读