手把手搭建千萬級Java算法測試-斐波那契額數列的三種實現方法比較

語言: CN / TW / HK

  今天開始呢,我們講解斐波那契額數列的三種實現方法,從算法思路,到算法偽代碼實現,到複雜度分析,從這裏開始我們手把手搭建一個測試平台的基礎,根據你自身硬件水平可以對下列代碼進行從1000,到千萬級測試,其中算法測試時間與你的機器硬件水平和實現的算法有關係,下面是斐波那契額數列的三種實現方法的具體講解。

(1)排序算法的思路

用樸素遞歸算法計算Fibonacci數列;

用自底向上算法計算Fibonacci數列;

用分治算法計算Fibonacci數列;

(2)算法偽代碼

c //樸素遞歸: 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階的方陣,由線代知識不難證明: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)代碼主體部分

```java 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)測試結果如下:

8.jpg

  本文重在算法討論,所有不再展示結果,注重算法的運行時間,筆者有興趣可以嘗試千萬級的算法測試,這裏便不在贅述。