java - 使用大整数时间复杂度的递归斐波那契数列

Question

你能解释一下下面算法的复杂性吗？

public BigInteger fibBigInt() {
    return fibBigInt( 
               BigInteger.valueOf(n), 
               ONE, 
               BigInteger.valueOf(0));
}

private BigInteger fibBigInt(BigInteger start, BigInteger val, BigInteger previous) {
    if (start.compareTo(BigInteger.valueOf(0)) == 0) {
        return previous;
    }
    return fibBigInt( 
               start.subtract(ONE),  
               val.add(previous), 
               val);
}

这个递归是如何在 O(n) 时间内运行的？我有点困惑。

Answer 1

Fibonacci 是不同复杂度类别的标准示例，因为根据定义的天真方法采用 O(2^n)时间，因为有一个线性解决方案只需要 O(n)时间。这个适用于线性模式。
这个想法是有一个起始值( fib(0) 和 fib(1) )并迭代计算 fib(n+2)来自 fib(n+1)通过一次调用它。诀窍是不仅要存储来自 fib(n+1) 的结果但来自 fib(n)以及。这是通过“旋转” fib(n+1) 的值来完成的。和 fib(n)在每个递归步骤中。
所以最好用一个例子来解释这是如何工作的(n =5)。请注意参数 m是您想要的斐波那契数的输入值。 m值递减，值 0 标志着递归结束。您截断的代码与计数器一起运行 m并且没有属性 n .

nmfib(n+1)fib(n)评论


0
5
1
0
代码的前 6 行

1
4
1+0 = 1
1
迭代步骤，代码的最后 4 行。当前fib(n+1)是 fib(n+1) + fib(n)从上面的行，fib(n)是 fib(n+1)从上面的行。

2
3
1+1 = 2
1
看上面

3
2
2+1 = 3
2

4
1
3+2 = 5
3

5
0
5+3 = 8
5
现在术语 start.compareTo(BigInteger.valueOf(0))变为 0，因此 fib(n) 的值(5) 将通过每次递归调用返回并“转发”回来。


这种方法显然是线性的，因此在 O(n) 中运行.