[理工] 遞迴時間函數

看板Grad-ProbAsk作者 (a shit)時間6年前 (2017/12/30 16:40), 編輯推噓4(4推 0噓 3→)
留言7則, 4人參與, 6年前最新討論串1/1
http://i.imgur.com/9OfmMyT.jpg
想請問這題的(b), 寫成T(n) = T(n-1) + T(n-2) + 1這樣對嗎？ 是用遞迴樹來解嗎？ 求提示 ----- Sent from JPTT on my Asus ASUS_Z017DA. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.8.99.193 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1514623252.A.3E0.html
推
12/30 16:51, 6年前 , 1F
N-2會call兩次吧？
12/30 16:51, 1F
→
12/30 17:00, 6年前 , 2F
對！！ 所以T(n-2)的係數是2，但這題是用遞迴樹來解
12/30 17:00, 2F
→
12/30 17:00, 6年前 , 3F
嗎？
12/30 17:00, 3F
推
12/30 17:53, 6年前 , 4F
可以用離散的遞迴來解
12/30 17:53, 4F
→
12/30 20:29, 6年前 , 5F
thanks
12/30 20:29, 5F
推
12/31 16:40, 6年前 , 6F
想問為什麼空間不是O(1) 不是只有用到count而已嗎
12/31 16:40, 6F
推
12/31 16:51, 6年前 , 7F
遞迴會把變數push到stack啊
12/31 16:51, 7F
‣ 更多 V1V1V1V1V1V 的文章
文章代碼(AID): #1QHr4KFW (Grad-ProbAsk)