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

  第八天开始呢，我们讲解斐波那契额数列的三种实现方法，从算法思路，到算法伪代码实现，到复杂度分析，从这里开始我们手把手搭建一个测试平台的基础，根据你自身硬件水平可以对下列代码进行从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);
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

（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阶的方阵，由线代知识不难证明：2x2的矩阵 {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");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

  往期对应的代码中SortHelper类我们留一个小小的悬念，留到最后来进行叙说，其中目前来说他的方法generateRandomArray的参数为，（num，left，right）第一个参数参与算法生成的数量级，作为随机生成序列，它可以为千万，因为是long级别，left和right则为生成序列的大小范围，生成的序列为返回值类型为Integer[]。
（5）测试结果如下：

  本文重在算法讨论，所有不再展示结果，注重算法的运行时间，笔者有兴趣可以尝试千万级的算法测试，这里便不在赘述。