CC189

p45计算Big O

int f(int n){
    if(n <= 0){
      return 1;
    }
    return f(n - 1) + f(n -1);
  }

• 这个是O(2^N)复杂度，O（N）空间

p51

int factorial(int n){
    if(n < 0){
      return -1;
    }else if(n == 0){
      return 1;
    }else{
      return n * factorial(n - 1);
    }
  }

• 这个是O(N)复杂度，根据T(N) = T(N) + 1推出

p52

int fib(int n){
    if(n <= 0){
      return 0;
    }else if(n == 1){
      return 1;
    }else{
      return fib(n - 1)* fib(n - 2);
    }
  }

• 这是O(2^N)复杂度，容易理解

• 下面这个也是O(2^N)的复杂度!

void allFib(int n){
    for(int i = 0; i < n; i++){
      System.out.println(i + ": " + fib(i));
    }
  }
  int fib(int n){
    if(n <= 0){
      return 0;
    }else if(n == 1){
      return 1;
    }else{
      return fib(n - 1)* fib(n - 2);
    }
  }

• 注意不是O(N2^N),实际算出来前面不过是多了个系数 ＝ 2

void allFib(int n){
    int[] memo = new int[n + 1];
    for(int i = 0; i < n; i++){
      System.out.println(i + ": " + fib(i, memo));
    }
  }
  int fib(int n, int[] memo){
    if(n <= 0){
      return 0;
    }else if(n == 1){
      return 1;
    }else if(memo[n] > 0){ 
      return return memo[n];
    }
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
  }

• 这题的复杂度是O(N)，因为fib(n)只需要抓出fib(n-1) 和fib(n - 2)的结果相加就好，constant time的操作

• 体现了记忆化搜索的优势