By Long Luo
斐波那契数列 ( Fibonacci sequence \textit{Fibonacci sequence} Fibonacci sequence ) ,又称黄金分割数列,因数学家莱昂纳多·斐波那契( Leonardoda Fibonacci \textit{Leonardoda Fibonacci} 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 , 1 3 , 2 1 , 3 4 , 5 5 , 8 9 , 1 4 4 , 2 3 3 … …
这个数列从第 3 3 3 项开始,每一项都等于前两项之和。
斐波那契数的边界条件是 F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 和 F ( 1 ) = 1 F(1)=1 F ( 1 ) = 1 。当 n > 1 n>1 n > 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 )
算法一:暴力法
如果不需要求解特别大的数值,又对时间敏感的话,可以有投机取巧的方法:
1 2 3 4 5 6 7 8 9 10 11 12 class Solution { int [] fib_nums = { 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 , 1346269 , 2178309 , 3524578 , 5702887 , 9227465 , 14930352 , 24157817 , 39088169 , 63245986 , 102334155 , 165580141 , 267914296 , 433494437 , 701408733 , 1134903170 , 1836311903 }; public int fib (int n) { return fib_nums[n]; } };
复杂度分析
时间复杂度: O ( 1 ) O(1) O ( 1 )
空间复杂度: O ( n ) O(n) O ( n )
算法二: 递归(recursion)
显而易见斐波那契数列存在递归 关系,很容易想到使用递归方法 来求解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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 ) ,可见是指数 级的。
我们可以写出其实现递归树,如下所示:
1 2 3 4 5 6 7 8 9 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 ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public static int fib (int n) { int f[] = new int [n + 2 ]; int i; f[0 ] = 0 ; f[1 ] = 1 ; for (i = 2 ; i <= n; i++) { f[i] = f[i - 1 ] + f[i - 2 ]; } return f[n]; } }
复杂度分析:
时间复杂度:O ( n ) O(n) O ( n ) 。
空间复杂度:O ( n ) O(n) O ( n ) 。
算法四:记录值的动态规划实现
针对[算法二](#算法二: 递归(recursion)),我们可以将计算好的值存储起来以避免重复运算 ,如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static int [] dp = new int [10 ];public static int fib (int n) { if (n <= 1 ) { return n; } 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 ); } return dp[n] = first + second; }
复杂度分析
时间复杂度: O ( n ) O(n) O ( n )
空间复杂度: O ( n ) O(n) O ( n )
算法五: 空间优化的动态规划(Space Optimized)
[算法三](#算法三: 动态规划(dynamic programming))时间复杂度和空间复杂度都是 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 ) 。代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 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 ) 。
算法六:矩阵幂
使用矩阵快速幂的方法可以降低时间复杂度 。
首先我们可以构建这样一个递推关系:
[ 1 1 1 0 ] [ 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}
[ 1 1 1 0 ] [ F ( n ) F ( n − 1 ) ] = [ F ( n ) + F ( n − 1 ) F ( n ) ] = [ F ( n + 1 ) F ( n ) ]
因此:
[ F ( n + 1 ) F ( n ) ] = [ 1 1 1 0 ] 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 ) ] = [ 1 1 1 0 ] n [ F ( 1 ) F ( 0 ) ]
令:
M = [ 1 1 1 0 ] M = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right]
M = [ 1 1 1 0 ]
因此只要我们能快速计算矩阵 M M M 的 n n n 次幂,就可以得到 F ( n ) F(n) F ( n ) 的值。如果直接求取 M n M^n M n ,时间复杂度是 O ( n ) O(n) O ( n ) ,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 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 ]; } 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; } public static void power (int F[][], int n) { int i; int M[][] = new int [][]{{1 , 1 }, {1 , 0 }}; for (i = 2 ; i <= n; i++) { multiply(F, M); } } }
复杂度分析
时间复杂度: O ( n ) O(n) O ( n ) ,在于计算矩阵的 n n n 次幂。
空间复杂度: O ( 1 ) O(1) O ( 1 ) 。
算法七:矩阵快速幂(分治快速幂运算)
算法五的时间复杂度是 O ( n ) O(n) O ( n ) ,但可以降低到 O ( l o g n ) O(logn) O ( l o g n ) ,因为可以使用分治算法加快幂运算,加速这里 M n M^n M n 的求取。如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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 ( l o g n ) O(logn) O ( l o g n ) 。
空间复杂度: O ( l o g n ) O(logn) O ( l o g n ) ,函数栈。
算法八:斐波那契数新算法求解
这是另外一种求解斐波那契数的算法,证明如下:
1. 矩阵形式的通项
( F n + 2 F n + 1 ) = ( 1 , 1 1 , 0 ) ⋅ ( F n + 1 F n ) \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}
( F n + 2 F n + 1 ) = ( 1 , 1 , 1 0 ) ⋅ ( F n + 1 F n )
不妨令:A = ( 1 , 1 1 , 0 ) A=\begin{pmatrix} 1,&1 \\ 1,&0 \end{pmatrix} A = ( 1 , 1 , 1 0 ) ,F 1 = 1 F_1=1 F 1 = 1 ,F 0 = 0 F_0=0 F 0 = 0 ,证明:
A n = ( F n + 1 , F n F n , F n − 1 ) A^n=\begin{pmatrix} F_{n+1}, &F_n \\ F_n,&F_{n-1} \end{pmatrix}
A n = ( F n + 1 , F n , F n F n − 1 )
采用数学归纳法 进行证明,
当 k = 1 k=1 k = 1 时:
A 1 = ( F 2 , F 1 F 1 , F 0 ) A^1=\begin{pmatrix}F_{2},&F_1 \\ F_1,&F_{0} \end{pmatrix}
A 1 = ( F 2 , F 1 , F 1 F 0 )
显然成立!
当 k = n k=n k = n 时:
A n + 1 = A n ⋅ A = ( F n + 1 , F n F n , F n − 1 ) ⋅ ( 1 , 1 1 , 0 ) = ( F n + 2 , F n + 1 F n + 1 , F n ) 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}
A n + 1 = A n ⋅ A = ( F n + 1 , F n , F n F n − 1 ) ⋅ ( 1 , 1 , 1 0 ) = ( F n + 2 , F n + 1 , F n + 1 F n )
2. 偶数项和奇数项
因为 A n = ( F n + 1 , F n F n , F n − 1 ) A^n=\begin{pmatrix}F_{n+1}, &F_n \\ F_n, &F_{n-1} \end{pmatrix} A n = ( F n + 1 , F n , F n F n − 1 ) ,则有:
A 2 m = A m ⋅ A m A^{2m} = A^m \cdot A^m
A 2 m = A m ⋅ A m
因为:
A 2 m = ( F 2 m + 1 , F 2 m F 2 m , F 2 m − 1 ) A^{2m}= \begin{pmatrix} F_{2m+1}, &F_{2m} \\ F_{2m}, &F_{2m-1}\end{pmatrix}
A 2 m = ( F 2 m + 1 , F 2 m , F 2 m F 2 m − 1 )
所以:
A 2 m = ( F m + 1 , F m F m , F m − 1 ) ⋅ ( F m + 1 , F m F m , F m − 1 ) = ( F m + 1 2 + F m 2 , F m ( F m + 2 F m − 1 ) F m ( F m + 2 F m − 1 ) , F m 2 + F m − 1 2 ) 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}
A 2 m = ( F m + 1 , F m , F m F m − 1 ) ⋅ ( F m + 1 , F m , F m F m − 1 ) = ( F m + 1 2 + F m 2 , F m ( F m + 2 F m − 1 ) , F m ( F m + 2 F m − 1 ) F m 2 + F m − 1 2 )
所以有:
F 2 m + 1 = F m + 1 2 + F m 2 F_{2m+1}=F^2_{m+1}+F^2_{m}
F 2 m + 1 = F m + 1 2 + F m 2
F 2 m = F m ( F m + 2 F m − 1 ) F_{2m}=F_m(F_m+2F_{m-1})
F 2 m = F m ( F m + 2 F m − 1 )
3. 矩形形式求解Fib(n)
因为涉及到矩阵幂次,考虑到数的幂次的递归解法:
n n n 为奇数:n = 2 k + 1 n=2k+1 n = 2 k + 1
F n = F 2 k + 1 = F k + 1 2 + F k 2 F_n =F_{2k+1}= F^2_{k+1}+F^2_{k}
F n = F 2 k + 1 = F k + 1 2 + F k 2
F n + 1 = F 2 k + 2 = F k + 1 ( F k + 1 + 2 F k ) F_{n+1}=F_{2k+2}=F_{k+1}(F_{k+1}+2F_k)
F n + 1 = F 2 k + 2 = F k + 1 ( F k + 1 + 2 F k )
n n n 为偶数:n = 2 k n=2k n = 2 k
F n = F 2 k = F k ( F k + 2 F k − 1 ) = F k ( F k + 2 ( F k + 1 − F k ) ) F_n=F_{2k}=F_k(F_k+2F_{k-1})=F_k(F_k+2(F_{k+1}-F_k))
F n = F 2 k = F k ( F k + 2 F k − 1 ) = F k ( F k + 2 ( F k + 1 − F k ) )
F n + 1 = F 2 k + 1 = F k + 1 2 + F k 2 F_{n+1}=F_{2k+1}=F^2_{k+1}+F^2_{k}
F n + 1 = F 2 k + 1 = F k + 1 2 + F k 2
根据上述公式,我们可以写出如下代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static int MAX = 1000 ;public static int f[];public static int fib (int n) { if (n == 0 ) { return 0 ; } if (n == 1 || n == 2 ) { return (f[n] = 1 ); } if (f[n] != 0 ) { return f[n]; } int k = (n & 1 ) == 1 ? (n + 1 ) / 2 : n / 2 ; 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 ( log n ) 。
空间复杂度: O ( 1 ) O(1) O ( 1 ) 。
斐波那契数 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 ) ,可以写出这样的特征方程:
x 2 = x + 1 x^2=x+1
x 2 = x + 1
求得 x 1 = 1 + 5 2 x_1 = \frac{1+\sqrt{5}}{2} x 1 = 2 1 + 5 , x 2 = 1 − 5 2 x_2 = \frac{1-\sqrt{5}}{2} x 2 = 2 1 − 5 。设通解为 F ( n ) = c 1 x 1 n + c 2 x 2 n F(n)=c_1x_1^n+c_2x_2^n F ( n ) = c 1 x 1 n + c 2 x 2 n ,代入初始条件 F ( 0 ) = 0 F(0)=0 F ( 0 ) = 0 ,F ( 1 ) = 1 F(1)=1 F ( 1 ) = 1 ,得 c 1 = 1 5 c_1=\frac{1}{\sqrt{5}} c 1 = 5 1 ,c 2 = − 1 5 c_2=-\frac{1}{\sqrt{5}} c 2 = − 5 1 。
因此斐波那契数的通项公式如下:
F ( n ) = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) 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 ) = 5 1 [ ( 2 1 + 5 ) n − ( 2 1 − 5 ) n ]
得到通项公式之后,就可以通过公式直接求解第n n n 项。
1 2 3 4 5 6 7 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 ( l o g n ) O(logn) O ( l o g n )
空间复杂度: O ( 1 ) O(1) O ( 1 )
总结
通过上述,我们使用了9种算法来求解斐波那契数列,这9种方法综合了递归、迭代、数学等各方面知识,值得认真学习!
参考文献