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

看板Grad-ProbAsk作者 (信號)時間5年前 (2018/09/25 00:59), 5年前編輯推噓4(4推 0噓 11→)
留言15則, 4人參與, 5年前最新討論串1/1
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
推
09/25 01:22, 5年前 , 1F
是按照算的時間來算 照你的邏輯 如果回傳f(n-1)/f(n-1)
09/25 01:22, 1F
→
09/25 01:22, 5年前 , 2F
那不就T(n)=T(n-1)/T(n-1)+C = C
09/25 01:22, 2F
→
09/25 01:23, 5年前 , 3F
直接變常數 超神
09/25 01:23, 3F
※ 編輯: SIGNAL2017 (118.160.96.239), 09/25/2018 01:32:06
→
09/25 01:32, 5年前 , 4F
請問按照算的時間來算是什麼意思呢
09/25 01:32, 4F
推
09/25 07:49, 5年前 , 5F
f(k-1)/f(k-2)只是我要return的值
09/25 07:49, 5F
→
09/25 07:49, 5年前 , 6F
他是說我呼叫f(k-1)和f(k-2)之後再把他們相除
09/25 07:49, 6F
→
09/25 07:49, 5年前 , 7F
所以f(k-1)跟f(k-2)都會呼叫道所以是時間相加
09/25 07:49, 7F
→
09/25 07:49, 5年前 , 8F
通常並不是呼叫長怎樣時間就長怎樣
09/25 07:49, 8F
→
09/25 07:49, 5年前 , 9F
而是看你呼叫了什麼東西
09/25 07:49, 9F
了解，感謝大大，那我懂為何是時間相加了，那想再請問為何要寫出時間遞迴式去解時， 要寫常數的部分:2呢? 為何不是T(n)=T(n-1)+T(n-2)+C (設加一個constant) ※ 編輯: SIGNAL2017 (118.160.96.239), 09/25/2018 10:35:41
推
09/25 13:01, 5年前 , 10F
也可以啊 +C不是重點因為常數都能寫成O(1)再算時間的
09/25 13:01, 10F
→
09/25 13:01, 5年前 , 11F
時候不會看到這塊
09/25 13:01, 11F
推
09/25 15:15, 5年前 , 12F
T(n-1) //求f(n-1)的時間
09/25 15:15, 12F
→
09/25 15:16, 5年前 , 13F
T(n-2) //求f(n-2)的時間
09/25 15:16, 13F
→
09/25 15:16, 5年前 , 14F
+c //retern做加法跟除法O(1的時間)
09/25 15:16, 14F
→
09/25 23:40, 5年前 , 15F
了解，謝謝。
09/25 23:40, 15F
‣ 更多 SIGNAL2017 的文章
文章代碼(AID): #1RgHW3vR (Grad-ProbAsk)