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 的大作中提到】
: 问用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 的大作中提到】
:
: 两个解是一样的，不就差了一个位置。
|
|
