[理工] 资结 解时间复杂度问题

楼主: SIGNAL2017 (信号2017)   2018-09-25 00:59:44
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省略掉去解特征方程式?
作者: krusnoopy (push)   2018-09-25 01:22:00
是按照算的时间来算 照你的逻辑 如果回传f(n-1)/f(n-1)那不就T(n)=T(n-1)/T(n-1)+C = C直接变常数 超神
楼主: SIGNAL2017 (信号2017)   2018-09-25 01:32:00
请问按照算的时间来算是什么意思呢
作者: wilson50101 (我觉得我还不错啊)   2018-09-25 07:49:00
f(k-1)/f(k-2)只是我要return的值他是说我呼叫f(k-1)和f(k-2)之后再把他们相除所以f(k-1)跟f(k-2)都会呼叫道所以是时间相加通常并不是呼叫长怎样时间就长怎样而是看你呼叫了什么东西
作者: skyHuan (Huan)   2018-09-25 15:15:00
T(n-1) //求f(n-1)的时间T(n-2) //求f(n-2)的时间+c //retern做加法跟除法O(1的时间)
楼主: SIGNAL2017 (信号2017)   2018-09-25 23:40:00
了解,谢谢。

Links booklink

Contact Us: admin [ a t ] ucptt.com