algorithm - 树递归斐波那契算法需要线性空间?

标签 algorithm recursion tree language-agnostic automation

我知道斐波那契数列呈指数增长,因此递归算法所需的步数呈指数增长,但是 SICP v2 说树递归斐波那契算法需要线性空间,因为我们只需要跟踪上面的节点我们在树上。

我知道所需的步数随 Fib(n) 呈线性增长,但我还假设由于树呈指数级扩展,因此此事件所需的内存也需要呈指数级增长。有人可以解释为什么所需的内存只线性扩展到 N,而不是指数增长吗?

最佳答案

我猜这是在评估中使用应用顺序的结果。鉴于

(define (fib n)
(cond ((= n 0) 0) ((= n 1) 1) (else (+ fib (- n 1)) (fib (- n 2))))))

[来自计算机程序的结构和解释]

(fib 5) 的正常顺序评估将继续扩展,直到它到达原始表达式:

(+ (+ (+ (+ (fib 1) (fib 0)) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0) (fib 0)))

这将导致树的所有叶子都存储在内存中,这将需要与 n 呈指数相关的空间空间。

但是应用顺序求值应该以不同的方式进行,沿着一个分支驱动到两个叶子的原始表达式,然后上升分支并积累任何侧分支。这将导致 (fib 5) 的最大长度表达式为:

(+ (+ (+ (+ (fib 1) (fib 0)) (fib 1)) (fib 2)) (fib 3))

此表达式比正常顺序评估中使用的表达式短得多。该表达式的长度不受树中叶子数的影响,仅受树的深度影响。

这是我在 SICP 中盯着那句话看了比我愿意承认的时间更长的时间后的答案。

关于algorithm - 树递归斐波那契算法需要线性空间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27345652/

相关文章:

c++ - 从列表中找到最近的点到一个引用列表

java - Java中如何实现大整数减法?

Python 递归限制以及如何持续监控某些内容

c# - 需要递归查找。 DB 与 C# GUI

haskell - 给出一棵树,其中每个节点的值包含子节点的总和

c# - C#中的解析树

excel - 在每个 jar 的最大可能容量下,找到容纳最大数量 Wine 的最少 jar 数

string - 不考虑字符顺序的最长匹配子串

recursion - 对象不适用于 MIT 方案(不同的阿克曼函数)

python - 列出通用(非二元)列表树中叶子的所有路径