时间复杂度（斐波那契数列演变）

常见的算法的时间复杂度分为：
1，常数阶
常数阶算法运行的次数是一个常数，如5、20、100。常数阶算法时间复杂度通常用O(1)表示。例如：

/**
  * 时间复杂度为O(1)
  */
private void test(int i, int j) {
        i = i ^ j;
        j = i ^ j;
        i = i ^ j;
        System.out.println(i + "--" + j);
}

2，多项式阶
很多算法时间复杂度是多项式，通常用O(n)、O(n²)、O(n³)等表示。例如：

 /**
  * 时间复杂度为O(n²)
  */
private void test(int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum++;
            }
        }
        System.out.println(sum);
}

    /**
     * 计算后一个格子里的数量是前一个格子数量的两倍 求总和
     * 尾递归 时间复杂度为O(n)  空间复杂度为0(n)  
     *
     * @param start 每次增加的数量 初始第一个格子为1
     * @param n     n个格子
     * @param sum   总和
     * @return 总数
     */
    private long test(int start, int n, int sum) {
        if (n < 0) {
            return sum;
        } else {
            return test(2 * start, --n, sum += start);
        }
    }

3，指数阶
指数阶时间复杂度运行效率极差，程序往往像躲“魔鬼”一样避开它，常见的有O(2^{n)、O(n!)、O(n}n)等。使用这样的算法需要谨慎，例如斐波那契数列的正常递归实现

4，对数阶
对数阶时间复杂度运行效率较高，常见的有O(logn)，O(nlogn)等，例如：

    /**
     * 时间复杂度为O(log2n)
     */
    private long test(int n) {
        int i = 1;
        while (i < n) {
            i = i * 2;
        }
        return i;
    }

时间复杂度的大致排序为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2^n)<O(n!)<O(nn)

斐波那契数列
后一项是前两项之和， 1 1 2 3 5 8 13
1,指数阶实现：

    /**
     * 递归实现 （最后就是一堆1 相加）
     *  时间复杂度 0(n)=0(n-1)+O(n-2)+1
     * @param n 要获得的第几项的值
     * @return 返回第n项的值
     */
    private int fibonacciSequence(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return fibonacciSequence(n - 1) + fibonacciSequence(n - 2);
        }
    }

2,多项式阶实现：

/**
     * 时间复杂度为O(n) 同时空间复杂度也为O(n)
     *
     * @param n 要获得的第几项的值
     * @return 返回第n项的值
     */
    private int fibonacciSequence(int n) {
        if (n < 1) {
            return -1;
        }
        int[] a = new int[n];
        a[0] = 1;
        a[1] = 1;
        for (int i = 2; i < n; i++) {
            a[i] = a[i - 1] + a[i - 2];
        }
        return a[n - 1];
    }

算法优化（也可以使用尾递归）：

/**
     * 时间复杂度为O(n) 空间复杂度为O(1)
     *
     * @param n 要获得的第几项的值
     * @return 返回第n项的值
     */
    private int fibonacciSequence(int n) {
        int s1, s2;
        if (n < 1) {
            return -1;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        s1 = 1;
        s2 = 1;
        for (int i = 2; i < n; i++) {
            s2 = s1 + s2;
            s1 = s2 - s1;
        }
        return s2;
    }

3，对数阶

//fibonacciSequence(1,0,0,6)

/**
     * 时间复杂度 O(logn)  空间复杂度O(1)
     *
     * @param a
     * @param b
     * @param p
     * @param q
     * @param count 要取的位置
     * @return 要取的位置数字
     */
    private int fibonacciSequence(int a, int b, int p, int q, int count) {
        if (count == 0) {
            return b;
        } else if (count % 2 != 0) {
            return fibonacciSequence(b * p + a * q + a * p, b * p + a * q, p, q, count - 1);
        } else {
            return fibonacciSequence(a, b, p * p + q * q, q * q + 2 * p * q, count / 2);
        }
    }