求解斐波那契數(shù)列的時(shí)間復(fù)雜度？

Fibonacci數(shù)列

無窮數(shù)列1,1,2,3,5,8,13,21,34,55，···，稱為Fibonacci數(shù)列。它可以遞歸的定義為

1 n=0

F(n)= 1 n=1

F(n-1)+F(n-2) n>1

第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：

int Fibonacci ( intn)

{

If(n

ReturnFibonacci(n-1)+Fibonacci(n-2);

}

1+T(n-1)+T(n-2) n>1

Tn=

0 n

時(shí)間復(fù)雜度為指數(shù)時(shí)間O(kn)

非遞歸計(jì)算如下：

Int Fibonacci(int n)

{

If(n

else{

int a=b=1;

for(int i=0;i