Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
22 lines (15 sloc) 948 Bytes
(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))

a)

计算出第 n 个菲波那契数时,需要执行多少次加法?

采用隐式流的计算方法,和求 fibs 的迭代方式类似,而且前面求出的 fib 数值已经缓存下来,所以时间复杂度 O(n)

b)

证明:在实现(delay <exp>)时,直接(lambda () <exp>),不用memo-proc过程所提供的优化,所需加法步骤会指数倍地增加。

这时的效果和递归方式类似,在求第 n 个 fib 数时,需要重新计算前 n-1 个 fib 数,如果求第n个fib数时间用t(n)表示,那么 t(n) = t(n-1) + t(n-2) + O(1),利用主定理可以解得

t(n) = O(xn), 其中 x = (1+sqrt(5))/2,也就是黄金分割比的值。