斐波那契算法

一、最优算法 迭代

一个迭代，时间复杂度O(N)

 /**
   * 迭代法
   * 通过不断的交换f1 f2 fn的值 注意控制好边界
   * 
   * @param n
   * @return
   */
  public static int fib(int n) {
    int f0 = 0, f1 = 1;
    if (n <= 0) return 0;
    if (n == 1) return 1;
    int fn = 0;
    for (int i = 2; i <= n; i++) {
      fn = f0 + f1;
      f0 = f1;
      f1 = fn;
    }
    return fn;
  }

迭代的方式还有一种，就是用数组存起来，然后取array[n]

/**
   * 借助数组，
   * 
   * @param n
   * @return
   */
  public static int fib(int n) {
    int array[] = new int[n + 1];
    array[0] = 0;
    array[1] = 1;

    for (int i = 2; i <= n; i++) {
      array[i] = array[i - 1] + array[i - 2];
    }
    return array[n];
  }

二、最简单算法 递归

/**
   * 递归是有明显缺陷的 
   * 当数组过大的时候会出现StackOverFlow
   * 
   * @param n
   * @return
   */
  public static int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);

  }