练习 3.57

从书本 227 页的 fibs 定义以及 229 页的 fibs 图示分析可知,对于第 i 个斐波那契数,也即是 (stream-ref fibs i) ,需要对 (stream-ref fibs (- i 1))(stream-ref fibs (- i 2)) 进行一次加法。

对于使用记忆过程实现的,无重复的 fibs 来说,每个 (stream-ref fibs i) 只需要被计算一次,以后就可以根据记忆过程来直接返回计算结果。

因此,计算 (stream-ref fibs n) 总共需要 n 次加法,它产生的计算序列和书本 26 页的迭代版本的 fib 过程是一样的。

另一方面,如果使用不带记忆过程的 lambda 来实现 delay ,那么对于每个 (stream-ref fibs i) ,都要对 (stream-ref fibs (- i 1))(stream-ref fibs (- i 2)) 进行一次加法,而对 (stream-ref fibs (- i 1)) 的求值又引发 (stream-ref fibs (-i 2)(stream-ref fibs (- i 3)) 进行相加,以此类推,一直回溯到 01 为止,这一计算所产生的加法序列和书本 24 页指数级复杂度的递归 fib 过程产生的加法序列一样,因此这一实现所需的加法将指数倍地上升。

讨论

blog comments powered by Disqus