斐波那契递归实现

public static void fib(n){
    if(n <= 0){
     return n;
    }else{
        return fib(n - 1) + fib(n - 2)

    }
}

T(n) = O(0.5*2^n-1) = O(2^n) //指数阶

斐波那契for循环实现

public static void fib(n){

    if(n <= 1){  //1
        return n; //1
    }
    int fst = 0; //1
  int scd = 1; //1
    for(int i=0;i<;i++) //1 + n + n + 4n
    {
        int sum = fst + scd;
        fst = scd;
    scd = sum;
        return scd;
    }

}

T(n) = O(5 + 6n) = O(n) //线性阶