[理工] 資結 解時間複雜度問題

[SIGNAL2017 (信號)]

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

想請問關於圖中例題16一些問題:

1. 要解一個遞迴algo的時間複雜度似乎是直接從return的函式下手，根據題目return

的是f(n-1)/f(n-2)+3，所以應該是寫T(n)=T(n-1)/T(n-2)+C ，不知道為何解答是那

個形式?

2. 如果是解答:T(n)=T(n-1)+T(n-2)+1 的形式的話，想請問在解的時候是不是應該是先

化成T(n)=T(n-1)+T(n-2)+C，然後把C省略掉去解特徵方程式?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.96.239
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1537808387.A.E5B.html
推 krusnoopy: 是按照算的時間來算 照你的邏輯 如果回傳f(n-1)/f(n-1)
→ krusnoopy: 那不就T(n)=T(n-1)/T(n-1)+C = C
→ krusnoopy: 直接變常數 超神
※ 編輯: SIGNAL2017 (118.160.96.239), 09/25/2018 01:32:06
→ SIGNAL2017: 請問按照算的時間來算是什麼意思呢
推 wilson50101: f(k-1)/f(k-2)只是我要return的值
→ wilson50101: 他是說我呼叫f(k-1)和f(k-2)之後再把他們相除
→ wilson50101: 所以f(k-1)跟f(k-2)都會呼叫道所以是時間相加
→ wilson50101: 通常並不是呼叫長怎樣時間就長怎樣
→ wilson50101: 而是看你呼叫了什麼東西
了解，感謝大大，那我懂為何是時間相加了，那想再請問為何要寫出時間遞迴式去解時，
要寫常數的部分:2呢? 為何不是T(n)=T(n-1)+T(n-2)+C (設加一個constant)
※ 編輯: SIGNAL2017 (118.160.96.239), 09/25/2018 10:35:41
推 wilson50101: 也可以啊 +C不是重點因為常數都能寫成O(1)再算時間的
→ wilson50101: 時候不會看到這塊
推 skyHuan: T(n-1)     //求f(n-1)的時間
→ skyHuan: T(n-2)     //求f(n-2)的時間
→ skyHuan: +c     //retern做加法跟除法O(1的時間)
→ SIGNAL2017: 了解，謝謝。