为什么斐波那契递归过程工作这么久?
这是在OCaml中:
let rec fib n = if n<2 then n else fib (n-1) + fib (n-2);;
这是在Mathematica中:
Fib[n_] := If[n < 2, n, Fib[n - 1] + Fib[n - 2]]
这是在Java中:
public static BigInteger fib(long n) {
if( n < 2 ) {
return BigInteger.valueOf(n);
}
else {
return fib(n-1).add(fib(n-2));
}
}
对于n=100
它工作了很长时间,因为,我想,它会及时跟踪具有2^100
节点的树。
数字要生成,因此它可能只消耗 100 个内存寄存器和 100 个计算策略。
因此,可以优化执行。
这个任务是关于什么的,它是如何解决的?由于解决方案没有在 Mathematica 中实现,它可能不存在。关于这个问题的研究呢?
这是一个用来展示记忆价值的经典例子。所以,这是让它走得更快的一种方法。
(如果你只是想快速计算斐波那契,当然重写函数以非常快速地得到答案是非常容易的。从 0 开始,一直工作到 n,每次传递前 2 个斐波那契数。
我认为要走的路是记忆,就像@JeffreyScofield的答案一样。定义:
Fib2[n_] := Fib2[n] = If[n < 2, n, Fib2[n - 1] + Fib2[n - 2]]
检查:
Fib[30] // AbsoluteTiming
(* {9.202920, 832040} *)
Fib2[30] // AbsoluteTiming
(* {0., 832040} *)
Fib2[100] // AbsoluteTiming
(* {0.001000, 354224848179261915075} *)
对于递归斐波那契数列,即使对于 n=100,也不应该花费那么多时间来操作。无论是递归的还是迭代的,它仍然应该在 O(N) 时间内执行,因为它所做的只是总结在常量时间内完成的先前数字。计算大约需要多长时间?