c*********t 发帖数: 2921 | 1 问用recursive求fib(n)的复杂度,是不是和求fib(n)值本身的方法一样?
两种方法:
1.数学表达式:用特征值
fib本身F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
复杂度T(n) = T(n-1) + T(n-2), T(0) = 1, T(1) = 1
这两个的特征值都一样,就是因为初始值不一样,所以最后的系数不一样,对吧?
2. 如果用logn的方法,也可以,区别还是初始值,对吧?
谢谢! | g**********y 发帖数: 14569 | 2
两个解是一样的,不就差了一个位置。
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 问用recursive求fib(n)的复杂度,是不是和求fib(n)值本身的方法一样? : 两种方法: : 1.数学表达式:用特征值 : fib本身F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1 : 复杂度T(n) = T(n-1) + T(n-2), T(0) = 1, T(1) = 1 : 这两个的特征值都一样,就是因为初始值不一样,所以最后的系数不一样,对吧? : 2. 如果用logn的方法,也可以,区别还是初始值,对吧? : 谢谢!
| w****o 发帖数: 2260 | 3 gloomyturkey,
你说的很对,T(n) = F(n+1).
可是我想了一下,如何定义这个暴力fibonacci的复杂度?我的理解有如何:
1. 如果定义成暴力求fib的过程中调用f(0), f(1)的总共的次数的话,那么T(n) = T(n
-1)+T(n-2)
2. 可是如果定义成暴力求fib的过程中调用函数(进栈/出战)的次数的话,T(n) = T(n-
1)+T(n-2)+1
让我们列一下
T(0) = 1
T(1) = 1
T(2) = 2 呢还是3呢?如果按照第一个定义只是算调用f(0), f(1)的次数的话,T(2)=2,
可是如果按照第二种的定义,算上要求f(2),本身也有一次函数的调用的话,T(2)=3
同样的问题对任意一个n.
其实如果把f(n)的求解过程画成一个树的话,第一个定义是算这个树的所有 leaf node
的个数,第二个定义是算树中的所有node的个数。
到底是哪种?
【在 g**********y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 两个解是一样的,不就差了一个位置。
|
|