求解斐波那契数列的时间复杂度 分别用递归和非递归方法

斐波那契数列的时间复杂度可以从递归和非递归两种方法来分析。

1. 递归方法：

递归方法是最直观的方法，它通过不断地调用自身来计算斐波那契数列的值。递归方法的时间复杂度可以用递归树的思想来分析。

- 在递归树中，每个节点表示一次函数调用的数据规模。

- 斐波那契数列的递归方法中，每次调用会有两个递归子问题（求n-1和n-2的斐波那契数），即每个节点分成了两个子节点。

- 递归终止条件是n=0或n=1时直接返回1。

- 递归树的深度为n。

- 所以，递归方法的时间复杂度为O(2^n)。

2. 非递归方法：

非递归方法通过迭代的方式逐个计算斐波那契数列的值。时间复杂度取决于迭代的次数，可以用循环来实现。

- 非递归方法的时间复杂度为O(n)。因为需要迭代n次来计算斐波那契数列中的第n个数。

- 在每一次循环迭代中，只需要通过计算前两个数的和来得到当前数，因此时间复杂度为O(1)。

综上所述，斐波那契数列的递归方法的时间复杂度为O(2^n)，而非递归方法的时间复杂度为O(n)。非递归方法的时间复杂度更低，效率更高。

Fibonacci数列

无穷数列1,1,2,3,5,8,13,21,34,55，···，称为Fibonacci数列。它可以递归的定义为

1 n=0

F(n)= 1 n=1

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

第n个Fibonacci数可递归地计算如下：

int Fibonacci ( intn)

{

If(n

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

}

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

Tn=

0 n

时间复杂度为指数时间O(kn)

非递归计算如下：

Int Fibonacci(int n)

{

If(n

else{

int a=b=1;

for(int i=0;i