Fibonacci问题详解

针对fibonacci数列,从时空复杂度对其解法进行分析。

Definition

斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家Leonardoda Fibonacci以兔子繁殖为例子而引入,故又称兔子数列。

Fibonacci数列归纳如下:

  • f(1) = 1
  • f(2) = 1
  • f(n) = f(n – 1) + f(n – 2)

Solution

我们从时间复杂度和空间复杂度进行分析。

Solution1 递归解法

Time: O(2n), Space: O(1)

public in fibonacci(int n)
{
    if (n < 2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

当我们计算f(5)的时候,需要计算f(4)和f(3)。当我们计算f(4)的时候,需要计算f(3)和f(2)。

img
img

可以看到,f(3)重复计算了。我们可以用二叉树表示整个过程:

由图可知,树的高度为n,满二叉树的结点个数为2n-1,当然,上图中的树肯定不是满二叉树,但也可以看出来,该树的节点个数大于满二叉树节点数的一半,即(2n-1)/2,假设计算次数为T(n),可知(2n-1)/2 < T(n) < 2n-1.因此该算法的时间复杂度为O(2^n)。

Solution2 动态规划

Time: O(n), Space: O(n)

public int fibonacci_dp(int n)
{
    if (n < 2) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[n] = dp[n - 1] + dp[n - 2];
    return dp[n];
}

当n比较大的时候,会报出OufOfMemory的错误。我们可以优化一下空间复杂度,使空间复杂度为O(1)。

public int fibonacci_dp(int n)
{
    if (n < 2) return n;
    int a = 0;
    int b = 1;
    int res = 0;
    for (int i = 2; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}

Solution 矩阵法

Time: O(logn), Space: O(n2)

当时我就在OJ上碰到了要求用O(logn)解出斐波那契数列,属实想不出来。这种解法主要依赖下面的公式:

img

从而得到:

img

这样就可以将Fib数列转化成一个求矩阵幂的运算。

而求幂的运算可以通过快速幂的技巧达到时间复杂度为O(logn)。所谓快速幂,也是就是24=42的原理。因此整个代码如下:

public int fibonacci(int n) {
    if (n < 2) return n;
    int[][] matrix = new int[][]{{0 ,1}, {1, 1}};
    int[][] powMatrix = quickMatrixMul(matrix, n - 1);
    return powMatrix[0][1] + powMatrix[1][1];
}

private int[][] quickMatrixMul(int[][] matrix, int k) {
    if (k == 1) return matrix;
    int[][] res = quickMatrixMul(MatrixMul(matrix, matrix), k / 2);
    if (k % 2 == 0)
        return res;
    else
        return MatrixMul(res, matrix);
}

private int[][] MatrixMul(int[][] a, int[][] b) {
    int[][] res = new int[2][2];
    res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
    res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
    res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
    res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
    return res;
}

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号