斐波那契数列

// 0，1，1， 2，3，5，8，13，21，34，55...// 菲波那切数列
// 0，1，2， 3，4，5，6， 7， 8， 9， 10 //下标

该数列来自于1212年一个叫斐波那契的人提出的一个问题

一对兔子从出生到成熟需要一个月，成熟后一对兔子会生一对小兔子，那么不考虑兔子的死亡，一年后会有多少只兔子呢？

rabit.jpg

其规则为，某个月的兔子数量等于上个月+上上个月的兔子之和。

用函数表示就是 f(n) = f(n-1)+f(n-2);

• 写个算法来看下：

    public int fib (int n){
        if (n <= 1 ) { //跳出递归
            return n;
        }
        return fib(n-1) + fib(n-2);
    }

• 下面分析下时间复杂度

从计算规则上来看，成长规则基本可以用二叉树来表示，二叉树的时间复杂度为O（2ⁿ）考虑到兔子生长需要时间，可以理解最终要减去一个常数，对总体复杂度没太大影响，所以统一理解为O（2ⁿ）。

• 优化

通常来说排序算法最差的时间复杂度也就是O（n²）了，所以指数级的复杂度显然不能被接受，电脑上运行n=60 左右电脑基本就卡死了。因为计算量太大，且如果打断点去分析，会发现重复计算太多，有大量的可优化空间。

接下来分析下优化方案，既然某个数=前一个数+前前一个数的和，那么就需要两个变量存放这两个数，通过两个变量的不断变化最终加出想要的结果，两个数最终的值可以通过从初始值不断相加得到。

    public int fib2 (int n){
        int cun = 0; //当前值
        int next = 1; // 下一个数字的值
        for (int i = 2; i < n ; i++) { // 起始值已经占用了两个了 i从2开始
            int temp = next; //保存下一个数字的值
            next = cun +next; //计算下一个数字的值
            cun = temp; //当前值等于保存的值
        }
        return cun + next;  //返回当前值和下一个数字的和。
    }

至此时间复杂度优化为O（n）。

时间复杂度排序 O(1）<O(log₂n)<O(n)<O(nlog₂n)<O(n²) <O(n³) <O(2ⁿ) <O(n!)<O(nⁿ)