作者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/cn.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