求解斐波那契数列Fibonacci Numbers算法我掌握了9种你掌握了

2021-08-27 23:36 Linux技巧

斐波那契数列(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;
}
}

复杂度分析:

时间复杂度: 图片  。

空间复杂度: 图片

算法五:矩阵幂

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

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

图片

因此:

图片

令:

图片

因此只要我们能快速计算矩阵M的n次幂,就可以得到图片的值。如果直接求取M^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, 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);
}
}
}

复杂度分析

时间复杂度:图片,在于计算矩阵的n次幂。

空间复杂度:图片

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

算法五的时间复杂度是图片 ,但可以降低到 本文章转载自公众号:irefactoring


首页 - Linux 相关的更多文章: