例如,
查看计算第n个斐波那契数的代码:
fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
此代码的问题在于,对于任何大于15的数字(在大多数计算机中),它将生成堆栈溢出错误。
假设我们正在计算fib(10)。在此过程中,fib(5)被多次计算。是否有某种方法可以将其存储在内存中以便快速检索,从而提高递归速度?
我正在寻找一种可用于几乎所有问题的通用技术。
最佳答案
是的,您的见解是正确的。
这称为dynamic programming。通常,这是常见内存运行时的折衷方案。
对于fibo,您甚至不需要缓存所有内容:
[编辑]
这个问题的作者似乎正在寻找一种通用的缓存方法,而不是一种计算斐波那契的方法。搜索维基百科或查看其他海报的代码以获得此答案。这些答案在时间和记忆上都是线性的。
**这里是线性时间算法O(n),在内存中恒定**
in OCaml:
let rec fibo n =
let rec aux = fun
| 0 -> (1,1)
| n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
let (cur,prec) = aux n in prec;;
in C++:
int fibo(int n) {
if (n == 0 ) return 1;
if (n == 1 ) return 1;
int p = fibo(0);
int c = fibo(1);
int buff = 0;
for (int i=1; i < n; ++i) {
buff = c;
c = p+c;
p = buff;
};
return c;
};
这以线性时间执行。但是日志实际上是可能的!
Roo的程序也是线性的,但是速度较慢,并且使用内存。
这是对数算法O(log(n))
现在,对于日志记录时间算法(更快的方式),这是一个方法:
如果知道u(n),u(n-1),计算u(n + 1),u(n),则可以通过应用矩阵来完成:
| u(n+1) | = | 1 1 | | u(n) |
| u(n) | | 1 0 | | u(n-1) |
这样就可以了:
| u(n) | = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1) | | 1 0 | | u(0) | | 1 0 | | 1 |
计算矩阵的指数具有对数复杂度。
只需递归地实现这个想法:
M^(0) = Id
M^(2p+1) = (M^2p) * M
M^(2p) = (M^p) * (M^p) // of course don't compute M^p twice here.
您也可以将它对角线化(不难),您会在其特征值中找到黄金数及其共轭,结果将为您提供u(n)的精确数学公式。它包含那些特征值的幂,因此复杂度仍然是对数的。
通常以Fibo为例来说明动态编程,但是正如您所看到的,它并不是真正相关的。
@约翰:
我认为这与哈希无关。
@ John2:
地图有点一般吧?对于斐波那契情况,所有键都是连续的,因此向量是合适的,再次有更快的方法来计算斐波那契序列,请参阅那边的代码示例。
关于performance - 有没有办法通过记住子节点来加 express 归?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/23962/