通过时间复杂度来衡量斐波那契算法优异度

下面有两种斐波那契算法，

• 第一种简单但是时间复杂度高，2的n次方为指数爆炸，所以运算起来很慢
• 第二种为线性复杂度，看起来多但实际运算效率很高

 /* 0 1 1 2 3 5 8 13 21 34*/
 /* 0 1 2 3 4 5 6 7  8  9*/

    //递归，输入70的时候程序就卡了
    //时间复杂度：O(2^n)
    public static int fib1(int n) {
        if (n <= 1) return n;
        return fib1(n - 1) + fib1(n -2);
    }

    //输入70,不卡
    //时间复杂度：O(n)
    public static int fib2(int n) {
        if (n <= 1) return n;

        int x = 0;
        int y = 1;
        int sum = 0;
        for (int i = 0; i <= n - 2; i ++) {
            sum = x + y;
            x = y;
            y = sum;
        }
        return sum;
    }



    //精简下，使用两个变量
    //时间复杂度：O(n)
    public static int fib2(int n) {
        if (n <= 1) return n;

        int x = 0;
        int y = 1;
        for (int i = 0; i <= n - 2; i ++) {
            y = x + y;
            x = y - x;
        }
        return y;
    }