300字范文 > 求解斐波那契数列(Fibonacci Numbers)算法居然有9种你知道哪几种吗？

求解斐波那契数列(Fibonacci Numbers)算法居然有9种你知道哪几种吗？

时间：2020-11-01 15:39:43

By LongLuo

斐波那契数列(Fibonacci sequence)，又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0,1,1,2,3,5,8,13,21,34,55,89,144,233……0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……0,1,1,2,3,5,8,13,21,34,55,89,144,233……

这个数列从第3项开始，每一项都等于前两项之和。

斐波那契数的边界条件是F(0)=0F(0)=0F(0)=0和F(1)=1F(1)=1F(1)=1。当n>1n>1n>1时，每一项的和都等于前两项的和，因此有如下递推关系：

F(n)=F(n−1)+F(n−2)F(n)=F(n-1)+F(n-2) F(n)=F(n−1)+F(n−2)

算法一: 递归(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));}}

复杂度分析：

时间复杂度：T(n)=T(n−1)+T(n−2)T(n)=T(n-1)+T(n-2)T(n)=T(n−1)+T(n−2)，可见是指数级的。

我们可以写出其实现递归树，如下所示：

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)

可以看出其做了很多重复性的计算，因此对于数值比较大时，其性能是灾难性的。

空间复杂度：O(n)O(n)O(n)，函数递归栈。

算法二: 动态规划(dynamic programming)

因为斐波那契数列存在递推关系，因为也可以使用动态规划来实现。动态规划的状态转移方程即为上述递推关系，边界条件为F(0)F(0)F(0)和F(1)F(1)F(1)。

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 = 0int 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];}}

复杂度分析：

时间复杂度：O(n)O(n)O(n)。

空间复杂度：O(n)O(n)O(n)。

算法三：记录值的动态规划实现

针对算法二，我们可以将计算好的值存储起来以避免重复运算，如下所示：

// Initialize array of dppublic 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);}// Memoizationreturn dp[n] = first + second;}

复杂度分析

时间复杂度: O(n)O(n)O(n)

空间复杂度: O(n)O(n)O(n)

算法四: 空间优化的动态规划(Space Optimized)

算法二时间复杂度和空间复杂度都是O(n)O(n)O(n)，但由于F(n)F(n)F(n)只和F(n−1)F(n-1)F(n−1)与F(n−2)F(n-2)F(n−2)有关，因此可以使用滚动数组思想把空间复杂度优化成O(1)O(1)O(1)。代码如下所示:

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;}}

复杂度分析：

时间复杂度：O(n)O(n)O(n)。

空间复杂度：O(1)O(1)O(1)。

算法五：矩阵幂

使用矩阵快速幂的方法可以降低时间复杂度。

首先我们可以构建这样一个递推关系：

[1110][F(n)F(n−1)]=[F(n)+F(n−1)F(n)]=[F(n+1)F(n)]\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \begin{bmatrix} F(n) \\ F(n−1) \\ \end{bmatrix} = \begin{bmatrix} F(n)+F(n−1) \\ F(n) \\ \end{bmatrix} = \begin{bmatrix} F(n+1) \\ F(n) \\ \end{bmatrix} [1110][F(n)F(n−1)]=[F(n)+F(n−1)F(n)]=[F(n+1)F(n)]

因此：

[F(n+1)F(n)]=[1110]n[F(1)F(0)]\left[ \begin{matrix} F(n + 1)\\ F(n) \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] ^n \left[ \begin{matrix} F(1)\\ F(0) \end{matrix} \right] [F(n+1)F(n)]=[1110]n[F(1)F(0)]

令：

M=[1110]M = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] M=[1110]

因此只要我们能快速计算矩阵MMM的nnn次幂，就可以得到F(n)F(n)F(n)的值。如果直接求取MnM^nMn，时间复杂度是O(n)O(n)O(n)，

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, andputs 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 theresult in F[][]Note that this function is designed only for fib() and won't work as generalpower 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);}}}

复杂度分析

时间复杂度：O(n)O(n)O(n)，在于计算矩阵的nnn次幂。

空间复杂度：O(1)O(1)O(1)。

算法六：矩阵快速幂(分治快速幂运算)

算法五的时间复杂度是O(n)O(n)O(n)，但可以降低到O(log⁡n)O(\log n)O(logn)，因为可以使用分治算法加快幂运算，加速这里MnM^nMn的求取。如下所示：

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;}}

复杂度分析

时间复杂度：O(log⁡n)O(\log n)O(logn)。

空间复杂度：O(log⁡n)O(\log n)O(logn)，函数栈。

算法七：斐波那契数新算法求解

这是另外一种求解斐波那契数的算法，证明如下：

1. 矩阵形式的通项

(Fn+2Fn+1)=(1,11,0)⋅(Fn+1Fn)\begin{pmatrix} F_{n+2}\\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1,&1\\ 1,&0 \end{pmatrix} \cdot \begin{pmatrix} F_{n+1}\\ F_{n} \end{pmatrix} (Fn+2Fn+1)=(1,1,10)⋅(Fn+1Fn)

不妨令：A=(1,11,0)A=\begin{pmatrix} 1,&1\\ 1,&0 \end{pmatrix}A=(1,1,10)，F1=1F_1=1F1=1，F0=0F_0=0F0=0，证明：

An=(Fn+1,FnFn,Fn−1)A^n=\begin{pmatrix} F_{n+1},&F_n\\ F_n,&F_{n-1} \end{pmatrix} An=(Fn+1,Fn,FnFn−1)

采用数学归纳法进行证明，

1. 当k=1k=1k=1时：

A1=(F2,F1F1,F0)A^1=\begin{pmatrix}F_{2},&F_1 \\ F_1,&F_{0} \end{pmatrix} A1=(F2,F1,F1F0)

显然成立！

2. 当k=nk=nk=n时：

An+1=An⋅A=(Fn+1,FnFn,Fn−1)⋅(1,11,0)=(Fn+2,Fn+1Fn+1,Fn)A^{n+1}=A^n\cdot A=\begin{pmatrix} F_{n+1},&F_n \\ F_n,&F_{n-1} \end{pmatrix}\cdot \begin{pmatrix} 1,&1\\ 1,&0 \end{pmatrix}=\begin{pmatrix} F_{n+2},&F_{n+1}\\ F_{n+1},&F_{n} \end{pmatrix} An+1=An⋅A=(Fn+1,Fn,FnFn−1)⋅(1,1,10)=(Fn+2,Fn+1,Fn+1Fn)

2. 偶数项和奇数项

因为An=(Fn+1,FnFn,Fn−1)A^n=\begin{pmatrix}F_{n+1},&F_n \\ F_n,&F_{n-1} \end{pmatrix}An=(Fn+1,Fn,FnFn−1)，则有：

A2m=Am⋅AmA^{2m} = A^m \cdot A^m A2m=Am⋅Am

因为：

A2m=(F2m+1,F2mF2m,F2m−1)A^{2m}= \begin{pmatrix} F_{2m+1}, &F_{2m} \\ F_{2m}, &F_{2m-1}\end{pmatrix} A2m=(F2m+1,F2m,F2mF2m−1)

所以：

A2m=(Fm+1,FmFm,Fm−1)⋅(Fm+1,FmFm,Fm−1)=(Fm+12+Fm2,Fm(Fm+2Fm−1)Fm(Fm+2Fm−1),Fm2+Fm−12)A^{2m}= \begin{pmatrix} F_{m+1},&F_m\\ F_m,&F_{m-1} \end{pmatrix}\cdot \begin{pmatrix} F_{m+1},&F_m\\ F_m,&F_{m-1} \end{pmatrix} \\ = \begin{pmatrix} F^2_{m+1}+F^2_{m},&F_m(F_m+2F_{m-1})\\ F_m(F_m+2F_{m-1}),&F^2_m+F^2_{m-1} \end{pmatrix} A2m=(Fm+1,Fm,FmFm−1)⋅(Fm+1,Fm,FmFm−1)=(Fm+12+Fm2,Fm(Fm+2Fm−1),Fm(Fm+2Fm−1)Fm2+Fm−12)

所以有：

F2m+1=Fm+12+Fm2F2m=Fm(Fm+2Fm−1)F_{2m+1}=F^2_{m+1}+F^2_{m} \\ F_{2m}=F_m(F_m+2F_{m-1}) F2m+1=Fm+12+Fm2F2m=Fm(Fm+2Fm−1)

3. 矩形形式求解Fib(n)

因为涉及到矩阵幂次，考虑到数的幂次的递归解法：

nnn为奇数：n=2k+1n=2k+1n=2k+1

Fn=F2k+1=Fk+12+Fk2Fn+1=F2k+2=Fk+1(Fk+1+2Fk)F_n =F_{2k+1}= F^2_{k+1}+F^2_{k} \\ F_{n+1}=F_{2k+2}=F_{k+1}(F_{k+1}+2F_k) Fn=F2k+1=Fk+12+Fk2Fn+1=F2k+2=Fk+1(Fk+1+2Fk)

nnn为偶数：n=2kn=2kn=2k

Fn=F2k=Fk(Fk+2Fk−1)=Fk(Fk+2(Fk+1−Fk))Fn+1=F2k+1=Fk+12+Fk2F_n=F_{2k}=F_k(F_k+2F_{k-1})=F_k(F_k+2(F_{k+1}-F_k)) \\ F_{n+1}=F_{2k+1}=F^2_{k+1}+F^2_{k} Fn=F2k=Fk(Fk+2Fk−1)=Fk(Fk+2(Fk+1−Fk))Fn+1=F2k+1=Fk+12+Fk2

根据上述公式，我们可以写出如下代码：

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 computedif (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];}

复杂度分析

时间复杂度：O(log⁡n)O(\log n)O(logn)。

空间复杂度：O(1)O(1)O(1)。

算法八：通项公式(Using Formula)

斐波那契数F(n)F(n)F(n)是齐次线性递推，根据递推方程F(n)=F(n−1)+F(n−2)F(n)=F(n-1)+F(n-2)F(n)=F(n−1)+F(n−2)，可以写出这样的特征方程：

x2=x+1x^2=x+1 x2=x+1

求得x1=1+52x_1 = \frac{1+\sqrt{5}}{2}x1=21+5。设通解为F(n)=c1x1n+c2x2nF(n)=c_1x_1^n+c_2x_2^nF(n)=c1x1n+c2x2n，代入初始条件 F(0)=0F(0)=0F(0)=0，F(1)=1F(1)=1F(1)=1，得c1=15c_1=\frac{1}{\sqrt{5}}c1=51，c2=−15c_2=-\frac{1}{\sqrt{5}}c2=−51。

因此斐波那契数的通项公式如下：

F(n)=15[(1+52)n−(1−52)n]F(n)=\frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right] F(n)=51[(21+5)n−(21−5)n]

得到通项公式之后，就可以通过公式直接求解第nnn项。

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);}}

复杂度分析

时间复杂度: O(logn)O(logn)O(logn)

空间复杂度: O(1)O(1)O(1)

算法九：暴力法

如果不需要求解特别大的

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];}};