本文已参加[新人创造礼]活动，一同敞开创造之路。

今天开端呢，咱们解说斐波那契额数列的三种完成办法，从算法思路，到算法伪代码完成，到复杂度剖析，从这儿开端咱们手把手建立一个测验渠道的基础，依据你自身硬件水平可以对下列代码进行从1000，到千万级测验，其间算法测验时刻与你的机器硬件水平缓完成的算法有关系，下面是斐波那契额数列的三种完成办法的具体解说。

（1）排序算法的思路

用朴素递归算法计算Fibonacci数列；

用自底向上算法计算Fibonacci数列；

用分治算法计算Fibonacci数列；

（2）算法伪代码

//朴素递归：
Fibonacci(int n)
	If(n==1)
		Return 0
	If(n==2)
		Retuen 1
	N=Fibonacci(n-1)+ Fibonacci(n-2)
Return N
//自底向上：
Fibonacci(n)
A[0]=0
A[1]=1
For i=2 to n
	A[i]=A[i-1]+A[i]
Retuen A[n]
//分治法（矩阵）：
Fibonacci ( A, n)
{
    w= {1,0,0,1};//初始二维矩阵
    q=w;
    if(n == 0){
     return q;
}
    else if(n ==1){
     return A;
	}
    else if(n%2==0){
     return change(Fibonacci (A, n / 2), Fibonacci (A, n / 2));
	}
    else{
     return change(change(Fibonacci (A, (n - 1) / 2), Fibonacci (A, (n - 1) / 2)), A);
	}
}

（3）复杂度剖析

1、 每个算法时刻复杂度剖析

（1）朴素递归： 时刻复杂度就是每一层递归的求和次数加和，易得1+2+4+8+2^(k-1)，再利用等比数列求和：和为:2^(k-1) -1，其间k为n。当步长为2的时分，和为2^(n/2-1) -1用大O表示法表示代码的时刻复杂度为O（2^(n/2)）到O（2^n）之间。

（2）自底向上 ： 使用了若干个辅佐变量，迭代辗转相加，每次记录前一项，时刻复杂度为 (n)， 但空间复杂度降到了 (1)。

（3）分治法（矩阵）： 斐波那契数列在n大于等于三的时分严格遵守递推数列f(n) = f(n-1) + f(n-2)，而对于一个二阶的递推数列来说，咱们可以用矩阵乘法来表示，且状态矩阵是2阶的方阵，由线代知识不难证明：2×2的矩阵 {1,1,1,0} ^ n = {Fn+1,Fn,Fn,Fn-1}；因此，模仿”快速幂”算法得到以下： （F(N),F(N-1)）= (F(N-1),F(N-2))*A 不难剖析时刻复杂度为：O (lg n)

2.结论

分治法优于自底向上法优于朴素递归的办法。

（4）代码主体部分

package runoob;
public class Fibonacci {
    static long f1 = 1;//初始值
    static long f2 = 1;
    public static long Fibonacci_1(long count) {//递归
        long count2 = count;
        if (count2 == 0) {
            return f1;
        } else if (count2 == 1) {
            return f2;
        } else {
            return Fibonacci_1(count2 - 1) + Fibonacci_1(count2 - 2);
        }
    }
    public static long Fibonacci_2(long count) {//自底向上
        long next;
        long count1 = count;
        long a1 = f1;
        long b1 = f2;
        for (long i = 0; i < count1 - 1; i++) {
            next = a1 + b1;
            a1 = b1;
            b1 = next;
            //每五个换一行
        }
        return b1;
    }
    public static long[][] matrixMultiply(long[][] a, long[][] b) {
        int rows = a.length;
        int cols = b[0].length;//矩阵乘法的行宽列宽计算办法
        long[][] matrix = new long[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                for (int k = 0; k < a[i].length; k++) {
                    matrix[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return matrix;
    }
    public static long Fibonacci_3(long count) {//分治法
        long count4 = count;
        if (count4 < 1) {
            return -1;
        }
        if (count4 == 1 || count4 == 2) {
            return 1;
        }
        long[][] result = {{1}, {0}};
        long[][] tem = {{1, 1}, {1, 0}};
        while (count4 != 0) {
            if ((count4 & 1) == 1) {
                result = matrixMultiply(tem, result);
            }
            tem = matrixMultiply(tem, tem);
            count4 >>= 1;//位右移
        }
        return result[1][0];
    }
    public static void Fibonacci_text(long num) {
        long count = num;
        System.out.println("计算个数共："+num);
        long start = System.nanoTime();
        Fibonacci_1(count);
        long mid = System.nanoTime();
        System.out.println("递归法耗时为"+(mid-start)/1000+"ms");
        Fibonacci_2(count);
        long mid_2 = System.nanoTime();
        System.out.println("自底向上法耗时为"+(mid_2-mid)/1000+"ms");
        Fibonacci_3(count);
        long end = System.nanoTime();
        System.out.println("分治法耗时为"+(end-mid_2)/1000+"ms");
    }
}

往期对应的代码中SortHelper类咱们留一个小小的悬念，留到最后来进行叙说，其间现在来说他的办法generateRandomArray的参数为，（num，left，right）第一个参数参加算法生成的数量级，作为随机生成序列，它可认为千万，由于是long级别，left和right则为生成序列的巨细范围，生成的序列为返回值类型为Integer[]。

（5）测验结果如下：

手把手搭建千万级Java算法测试-斐波那契额数列的三种实现方法比较

本文重在算法讨论，一切不再展示结果，注重算法的运转时刻，笔者有兴趣可以尝试千万级的算法测验，这儿便不在赘述。