求暴力fibonacci的复杂度# JobHunting - 待字闺中
c*t
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的方法,也可以,区别还是初始值,对吧?
谢谢!
两种方法:
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的方法,也可以,区别还是初始值,对吧?
谢谢!