求暴力fibonacci的复杂度 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求暴力fibonacci的复杂度

求暴力fibonacci的复杂度# JobHunting - 待字闺中

c*t2012-03-27 07:03

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*y2012-03-27 07:03

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*o2012-03-27 07:03

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 的大作中提到】

:
: 两个解是一样的，不就差了一个位置。