Question

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

Answer 1

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<=1)return 1;
ReturnFibonacci(n-1)+Fibonacci(n-2);
}
1+T(n-1)+T(n-2) n>1
Tn=
0 n<=1

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

非递归计算如下：
Int Fibonacci(int n)
{
If(n<2)return 1;
else{
int a=b=1;
for(int i=0;i<n+2;i++)
{
b=a+b;
a=b-a;
return a+b;
}
}
}
时间复杂度为O(n).

Answer 2

转一个牛人的博客，链接：https://www.jianshu.com/p/91b47e5f333b；
讲的很清楚，递归可以近似为二叉树，非递归是for循环，这里防止博客过期，就crtl+c+v了= =;

function fibonacci(n) {     
    if (n <= 1) {          
        return n;     
    }     
    return fibonacci(n-1) + fibonacci(n-2); 
}

针对递归方法的教学，斐波那数列可能是最常用来拿来举例的了;
但是，实际计算时绝不推荐使用递归方法，很容易stack overflow;
可以在浏览器中计算个fibonacci(100)试试。而且其时间复杂度为指数级，可以近似认为是2^n, 当然准确点可能是1.6^n;

其时间复杂度的计算： 递推关系式为f(n)=f(n-1)+f(n-2);
显然是一个2阶常系数查分方程，其特征方程为x^2-x-1=0;
得其解x， 时间复杂度为O(1.618^n);

或者另一种思路： 该方法的递归求解过程其实就是其二叉树展开的过程，时间复杂度就是计算该二叉树的节点个数： 树高n层， 但不是满二叉树，忽略常数，是O(2^n)

将递归展开，以循环方式计算

function fibonacci(n) {
    if (n <= 1) {
            return n;
   }
       let one = 0;
       let two = 1; 
       let res;
       for (let i = 2; i <= n; i++){
           res = one + two;
           one = two;
           two = res;
   }    
   return res;
}

事件复杂度为O(n)

作者：RichardBillion
链接：https://www.jianshu.com/p/91b47e5f333b
来源：简书

Answer 3

这是递推算法又不是排序算法，就一个公式有什么时间复杂度，扯淡了

Answer 4

这是递推算法又不是排序算法，就一个公式有什么时间复杂度，扯淡了