使用大整数时间复杂度的递归斐波那契
Recursive fibonacci using Big Integer time complexity
能否解释一下下面算法的复杂度？
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) 时间内递归 运行？我有点糊涂了。
Fibonacci 是不同复杂度的标准示例 类，因为根据定义，天真的方法需要 O(2^n) 时间，而线性解决方案只需要 O(n) 时间。这个适用于线性模式。
这个想法是有一个起始值（fib(0) 和 fib(1)），并通过一次调用从 fib(n+1) 迭代计算 fib(n+2)。诀窍是不仅要存储 fib(n+1) 的结果，还要存储 fib(n) 的结果。这是通过在每个递归步骤中“旋转”fib(n+1) 和 fib(n) 的值来完成的。
因此最好用一个例子来解释它是如何工作的 (n=5)。请注意，参数 m 是您想要的斐波那契数的输入值。 m 的值在递减，值 0 标志着递归结束。您截取的代码使用计数器 m 运行并且没有属性 n.
nmfib(n+1)fib(n)comment
0
5
1
0
first 6 lines of your code
1
4
1+0 = 1
1
iteration step, last 4 lines of your code. The current fib(n+1) is the fib(n+1)+fib(n) from the line above, fib(n) is the fib(n+1) from the line above.
2
3
1+1 = 2
1
see above
3
2
2+1 = 3
2
4
1
3+2 = 5
3
5
0
5+3 = 8
5
now the term start.compareTo(BigInteger.valueOf(0)) becomes 0 and therefore the value for fib(n) (5) will be returned and "forwarded" back through each recursive call.
这种方法显然是线性的，因此在 O(n) 中运行。
能否解释一下下面算法的复杂度？
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) 时间内递归 运行？我有点糊涂了。
Fibonacci 是不同复杂度的标准示例 类，因为根据定义，天真的方法需要 O(2^n) 时间，而线性解决方案只需要 O(n) 时间。这个适用于线性模式。
这个想法是有一个起始值（fib(0) 和 fib(1)），并通过一次调用从 fib(n+1) 迭代计算 fib(n+2)。诀窍是不仅要存储 fib(n+1) 的结果，还要存储 fib(n) 的结果。这是通过在每个递归步骤中“旋转”fib(n+1) 和 fib(n) 的值来完成的。
因此最好用一个例子来解释它是如何工作的 (n=5)。请注意，参数 m 是您想要的斐波那契数的输入值。 m 的值在递减，值 0 标志着递归结束。您截取的代码使用计数器 m 运行并且没有属性 n.
n |
m |
fib(n+1) |
fib(n) |
comment |
|---|---|---|---|---|
| 0 | 5 | 1 | 0 | first 6 lines of your code |
| 1 | 4 | 1+0 = 1 | 1 | iteration step, last 4 lines of your code. The current fib(n+1) is the fib(n+1)+fib(n) from the line above, fib(n) is the fib(n+1) from the line above. |
| 2 | 3 | 1+1 = 2 | 1 | see above |
| 3 | 2 | 2+1 = 3 | 2 | |
| 4 | 1 | 3+2 = 5 | 3 | |
| 5 | 0 | 5+3 = 8 | 5 | now the term start.compareTo(BigInteger.valueOf(0)) becomes 0 and therefore the value for fib(n) (5) will be returned and "forwarded" back through each recursive call. |
这种方法显然是线性的，因此在 O(n) 中运行。