By LongLuo

斐波那契數列(Fibonacci sequence)，又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：

這個數列從第3項開始，每一項都等于前兩項之和。

斐波那契數的邊界條件是和。當時，每一項的和都等于前兩項的和，因此有如下遞推關系：

顯而易見斐波那契數列存在遞歸關系，很容易想到使用遞歸方法來求解：

public class Solution { public static int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) fib(n - 2); } public static void main(String[] args) { System.out.println("1 ?= " fib(1)); System.out.println("1 ?= " fib(2)); System.out.println("2 ?= " fib(3)); } }

時間複雜度：，可見是指數級的。

我們可以寫出其實現遞歸樹，如下所示：

fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) fib(1) fib(0) fib(1) fib(0) / \ fib(1) fib(0)

可以看出其做了很多重複性的計算，因此對于數值比較大時，其性能是災難性的。

空間複雜度：，函數遞歸棧。

因為斐波那契數列存在遞推關系，因為也可以使用動态規劃來實現。動态規劃的狀态轉移方程即為上述遞推關系，邊界條件為和。

class Solution { public static int fib(int n) { /* Declare an array to store Fibonacci numbers. */ int f[] = new int[n 2]; // 1 extra to handle case, n = 0 int i; /* 0th and 1st number of the series are 0 and 1*/ f[0] = 0; f[1] = 1; for (i = 2; i <= n; i ) { /* Add the previous 2 numbers in the series and store it */ f[i] = f[i - 1] f[i - 2]; } return f[n]; } }

時間複雜度：。空間複雜度：。

針對算法二，我們可以将計算好的值存儲起來以避免重複運算，如下所示：

// Initialize array of dp public static int[] dp = new int[10]; public static int fib(int n) { if (n <= 1) { return n; } // Temporary variables to store values of fib(n-1) & fib(n-2) int first, second; if (dp[n - 1] != -1) { first = dp[n - 1]; } else { first = fib(n - 1); } if (dp[n - 2] != -1) { second = dp[n - 2]; } else { second = fib(n - 2); } // Memoization return dp[n] = first second; }

時間複雜度:空間複雜度:

算法二時間複雜度和空間複雜度都是，但由于隻和與有關，因此可以使用滾動數組思想把空間複雜度優化成。代碼如下所示:

class Solution { public int fib(int n) { if (n < 2) { return n; } int p = 0, q = 0, r = 1; for (int i = 2; i <= n; i) { p = q; q = r; r = p q; } return r; } }

時間複雜度：。空間複雜度：。

使用矩陣快速幂的方法可以降低時間複雜度。

首先我們可以構建這樣一個遞推關系：

因此：

令：

因此隻要我們能快速計算矩陣的次幂，就可以得到的值。如果直接求取，時間複雜度是，

class Solution { public static int fib(int n) { int F[][] = new int[][]{{1, 1}, {1, 0}}; if (n == 0) { return 0; } power(F, n - 1); return F[0][0]; } /* Helper function that multiplies 2 matrices F and M of size 2*2, and puts the multiplication result back to F[][] */ public static void multiply(int F[][], int M[][]) { int x = F[0][0] * M[0][0] F[0][1] * M[1][0]; int y = F[0][0] * M[0][1] F[0][1] * M[1][1]; int z = F[1][0] * M[0][0] F[1][1] * M[1][0]; int w = F[1][0] * M[0][1] F[1][1] * M[1][1]; F[0][0] = x; F[0][1] = y; F[1][0] = z; F[1][1] = w; } /* Helper function that calculates F[][] raise to the power n and puts the result in F[][] Note that this function is designed only for fib() and won't work as general power function */ public static void power(int F[][], int n) { int i; int M[][] = new int[][]{{1, 1}, {1, 0}}; // n - 1 times multiply the matrix to {{1,0},{0,1}} for (i = 2; i <= n; i ) { multiply(F, M); } } }

時間複雜度：，在于計算矩陣的次幂。空間複雜度：。

算法五的時間複雜度是，但可以降低到，因為可以使用分治算法加快幂運算，加速這裡的求取。如下所示：

class Solution { public int fib(int n) { if (n < 2) { return n; } int[][] q = {{1, 1}, {1, 0}}; int[][] res = pow(q, n - 1); return res[0][0]; } public int[][] pow(int[][] a, int n) { int[][] ret = {{1, 0}, {0, 1}}; while (n > 0) { if ((n & 1) == 1) { ret = multiply(ret, a); } n >>= 1; a = multiply(a, a); } return ret; } public int[][] multiply(int[][] a, int[][] b) { int[][] c = new int[2][2]; for (int i = 0; i < 2; i ) { for (int j = 0; j < 2; j ) { c[i][j] = a[i][0] * b[0][j] a[i][1] * b[1][j]; } } return c; } }

時間複雜度：。空間複雜度：，如果認為函數棧也算空間的話。

這是另外一種求解斐波那契數的算法，證明如下：

不妨令：，，，

證明：

采用數學歸納法進行證明，

顯然成立！

因為，則有：

所以有：

因為涉及到矩陣幂次，考慮到數的幂次的遞歸解法：

為奇數：

為偶數：

根據上述公式，我們可以寫出如下代碼：

public static int MAX = 1000; public static int f[]; // Returns n'th fibonacci number using // table f[] public static int fib(int n) { if (n == 0) { return 0; } if (n == 1 || n == 2) { return (f[n] = 1); } // If fib(n) is already computed if (f[n] != 0) { return f[n]; } int k = (n & 1) == 1 ? (n 1) / 2 : n / 2; // Applying above formula [Note value n&1 is 1 if n is odd, else 0. f[n] = (n & 1) == 1 ? (fib(k) * fib(k) fib(k - 1) * fib(k - 1)) : (2 * fib(k - 1) fib(k)) * fib(k); return f[n]; }

時間複雜度：。空間複雜度：。

斐波那契數是齊次線性遞推，根據遞推方程，可以寫出這樣的特征方程：

求得。

設通解為，代入初始條件，，得

，。

因此斐波那契數的通項公式如下：

得到通項公式之後，就可以通過公式直接求解第項。

class Solution { public int fib(int n) { double sqrt5 = Math.sqrt(5); double fibN = Math.pow((1 sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n); return (int) Math.round(fibN / sqrt5); } }

時間複雜度:空間複雜度:

如果不需要求解特别大的

class Solution { public: int fib(int n) { int nums[31]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040}; return nums[n]; } };

時間複雜度:空間複雜度:

通過上述，我們使用了9種算法來求解斐波那契數列，這9種方法綜合了遞歸、叠代、數學等各方面知識，值得認真學習！

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!