作者SIGNAL2017 (信號)
看板Grad-ProbAsk
標題[理工] 資結 解時間複雜度問題
時間Tue Sep 25 00:59:44 2018
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1537808387.A.E5B.html
1F：推 krusnoopy: 是按照算的時間來算 照你的邏輯 如果回傳f(n-1)/f(n-1) 09/25 01:22
2F：→ krusnoopy: 那不就T(n)=T(n-1)/T(n-1)+C = C 09/25 01:22
3F：→ krusnoopy: 直接變常數 超神 09/25 01:23
※ 編輯: SIGNAL2017 (118.160.96.239), 09/25/2018 01:32:06
4F：→ SIGNAL2017: 請問按照算的時間來算是什麼意思呢 09/25 01:32
5F：推 wilson50101: f(k-1)/f(k-2)只是我要return的值 09/25 07:49
6F：→ wilson50101: 他是說我呼叫f(k-1)和f(k-2)之後再把他們相除 09/25 07:49
7F：→ wilson50101: 所以f(k-1)跟f(k-2)都會呼叫道所以是時間相加 09/25 07:49
8F：→ wilson50101: 通常並不是呼叫長怎樣時間就長怎樣 09/25 07:49
9F：→ wilson50101: 而是看你呼叫了什麼東西 09/25 07:49
了解，感謝大大，那我懂為何是時間相加了，那想再請問為何要寫出時間遞迴式去解時，
要寫常數的部分:2呢? 為何不是T(n)=T(n-1)+T(n-2)+C (設加一個constant)
※ 編輯: SIGNAL2017 (118.160.96.239), 09/25/2018 10:35:41
10F：推 wilson50101: 也可以啊 +C不是重點因為常數都能寫成O(1)再算時間的 09/25 13:01
11F：→ wilson50101: 時候不會看到這塊 09/25 13:01
12F：推 skyHuan: T(n-1) //求f(n-1)的時間 09/25 15:15
13F：→ skyHuan: T(n-2) //求f(n-2)的時間 09/25 15:16
14F：→ skyHuan: +c //retern做加法跟除法O(1的時間) 09/25 15:16
15F：→ SIGNAL2017: 了解，謝謝。 09/25 23:40