By LongLuo
斐波那契數列(Fibonacci sequence),又稱黃金分割數列,因數學家萊昂納多·斐波那契(Leonardoda Fibonacci)以兔子繁殖為例子而引入,故又稱為“兔子數列”,指的是這樣一個數列:
這個數列從第3項開始,每一項都等于前兩項之和。
斐波那契數的邊界條件是和。當時,每一項的和都等于前兩項的和,因此有如下遞推關系:
算法一: 遞歸(recursion)顯而易見斐波那契數列存在遞歸關系,很容易想到使用遞歸方法來求解:
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)
可以看出其做了很多重複性的計算,因此對于數值比較大時,其性能是災難性的。
空間複雜度:,函數遞歸棧。
算法二: 動态規劃(dynamic programming)因為斐波那契數列存在遞推關系,因為也可以使用動态規劃來實現。動态規劃的狀态轉移方程即為上述遞推關系,邊界條件為和。
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;
}
時間複雜度:空間複雜度:
算法四: 空間優化的動态規劃(Space Optimized)算法二時間複雜度和空間複雜度都是,但由于隻和與有關,因此可以使用滾動數組思想把空間複雜度優化成。代碼如下所示:
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;
}
}
時間複雜度:。空間複雜度:,如果認為函數棧也算空間的話。
算法七:斐波那契數新算法求解這是另外一種求解斐波那契數的算法,證明如下:
1. 矩陣形式的通項不妨令:,,,
證明:
采用數學歸納法進行證明,
1. 當時:顯然成立!
2. 當時:2. 偶數項和奇數項因為,則有:
所以有:
3. 矩形形式求解Fib(n)因為涉及到矩陣幂次,考慮到數的幂次的遞歸解法:
為奇數:
為偶數:
根據上述公式,我們可以寫出如下代碼:
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];
}
時間複雜度:。空間複雜度:。
算法八:通項公式(Using Formula)斐波那契數是齊次線性遞推,根據遞推方程,可以寫出這樣的特征方程:
求得。
設通解為,代入初始條件,,得
,。
因此斐波那契數的通項公式如下:
得到通項公式之後,就可以通過公式直接求解第項。
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每日頭條,我们将持续为您更新最新资讯!