[理工] 遞迴時間函數 V1V1V1V1V1V PTT批踢踢實業坊

[理工] 遞迴時間函數

作者: V1V1V1V1V1V (a shit) 2017-12-30 16:40:50

http://i.imgur.com/9OfmMyT.jpg
想請問這題的(b),
寫成T(n) = T(n-1) + T(n-2) + 1這樣對嗎？
是用遞迴樹來解嗎？
求提示

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

N-2會call兩次吧？

作者: V1V1V1V1V1V (a shit) 2017-12-30 17:00:00

對！！所以T(n-2)的係數是2，但這題是用遞迴樹來解嗎？

作者: NeoHiphop (政大附中98年入學) 2017-12-30 17:53:00

可以用離散的遞迴來解

作者: V1V1V1V1V1V (a shit) 2017-12-30 20:29:00

thanks

作者: kobebset105 (小小小妹) 2017-12-31 16:40:00

想問為什麼空間不是O(1) 不是只有用到count而已嗎

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

遞迴會把變數push到stack啊

繼續閱讀

[理工] pipelinekobebset105 [商管] 線代wangborwai [理工] 106台大工數C PDE邊界問題poyin0820 [理工] 102中央線代qwer911 [理工] 離散全序關係MOUOREO 離散 adjacency matrixjp860316 [理工] 101 台大資工軟體數題s1020824 [理工] os page&frame&pagetableawayscute [理工] OSkobebset105 [理工] 工數 PDEpttrzong

Contact Us: admin [ a t ] ucptt.com