```java package net.zhaoxuyang.common.algorithm.other; /** * 暴力遞歸，記憶搜索，矩陣求法，流處理求斐波那契數列 * 結論： * （1）流處理并沒有想象中的快 * （2）暴力遞歸效率及其低下，N稍微大點（40左右）就已經算不出結果 * （3）矩陣求法并沒有記憶搜索快，但是在計算量較大的【別的程序】中卻是最快的 */ import java.util.stream.Stream; /** * * @author zhaoxuyang */ public class Fibonacci { public static void main(String[] args) throws InterruptedException { int n = 50; int res; long start; // start = System.nanoTime(); // res = f1(n); // System.out.println(res); // System.out.println(System.nanoTime() - start); start = System.nanoTime(); res = f2(n); System.out.println(res); System.out.println(System.nanoTime() - start); start = System.nanoTime(); res = f3(n); System.out.println(res); System.out.println(System.nanoTime() - start); start = System.nanoTime(); res = Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]}) .skip(n) .map(t -> t[0]) .findFirst() .get(); System.out.println(res); System.out.println(System.nanoTime() - start); /* n=20時，輸出 6765 705588 6765 21391 6765 38888 6765 72026229 n=100時，注釋掉O(2^N)的第一段因為要很久時間，所以后三個的輸出 -980107325 166519 -980107325 43165 -980107325 72650035 */ } /** * O(2^N) * * @param n * @return */ public static int f1(int n) { if (n < 1) { return 0; } else if (n == 1 || n == 2) { return 1; } else { return f1(n - 1) + f1(n - 2); } } /** * 記憶搜索 O(N) * * @param n * @return */ public static int f2(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return 1; } int res = 1; int pre = 1; for (int i = 3; i <= n; i++) { int tmp = res; res = res + pre; pre = tmp; } return res; } /** * 矩陣求法 O(logN) * <pre> * 如果遞歸式嚴格遵循F(N)=F(N-1)+F(N-2)， * 對于求第N項值，有矩陣乘法的方式可以將時間復雜度降至O(ogN) * 二階遞推數列，狀態矩陣為2*2的矩陣： * * (F(n),F(n-1)) = (F(n-1),F(n-2)) * | a b | * | c d | * 斐波那契數列的前4項代入求出狀態矩陣： * | a b | | 1 1 | * | c d | = | 1 0 | * * (F(n),F(n-1)) = (F(n-1), F(n-2)) * | 1 1 | = (1,1) * | 1 1 |^(n-2) * | 1 0 | | 1 0 | * 問題變成求矩陣N次方 * 以整數10的75次方為例： * 75的二進制為1001011，則10的75次方=10^64 * 10^8 * 10^2 * 10^1 * 把累乘的值相乘即可 * * 對于矩陣，求矩陣m的p次方請參看matrixPower方法，其中muliMatrix是兩個矩陣相乘的具體實現 * </pre> * * @param n * @return */ public static int f3(int n) { if (n < 1) { return 0; } if (n == 1 || n == 2) { return 1; } int[][] base = {{1, 1}, {1, 0}}; int[][] res = matrixPower(base, n - 2); return res[0][0] + res[1][0]; } /** * @param m * @param p * @return */ private static int[][] matrixPower(int[][] m, int p) { int[][] res = new int[m.length][m[0].length]; for (int i = 0; i < res.length; i++) { res[i][i] = 1; } int[][] tmp = m; for (; p != 0; p >>= 1) { if ((p & 1) != 0) { res = muliMatrix(res, tmp); } tmp = muliMatrix(tmp, tmp); } return res; } private static int[][] muliMatrix(int[][] m1, int[][] m2) { int[][] res = new int[m1.length][m2[0].length]; for (int i = 0; i < m2[0].length; i++) { for (int j = 0; j < m1.length; j++) { for (int k = 0; k < m2.length; k++) { res[i][j] += m1[i][k] * m2[k][j]; } } } return res; } } ```