CG@CPPBLOG

/*=========================================*/
随笔 - 76, 文章 - 39, 评论 - 137, 引用 - 0
数据加载中……

我的SICP习题答案（1.14~1.15）

1.14
计算过程的树如下：


很容易看出，计算过程的空间需求，也就是树的深度，取决于最左边的子树，即(n 1)，它的深度是n+6，O(n).

然后对于计算步数，也就是树的节点数，我们知道对于一个二叉树，树的节点数 = 左子树节点数 + 右子树节点数 + 1.
先来看 (n 1) 子树，设它的节点数是f(n), 而且总有，非叶节点左子树节点数为1
当 n=1，f(1) = 3
   n>1, f(n) = 1 + f(n-1) + 1 = f(n-1) + 2 = f(n-2) + 2*2
             = f(n-(n-1)) + 2*(n-1) = 2n + 1
             = O(n)

再来看 (n 2) 子树，设它的节点数 g(n), 设 ┌ n/5 ┐ = A
g(n) = f(n) + g(n-5) + 1 = f(n) + f(n-5) + g(n-5*2) + 2
     = f(n) + ... + f(n-5*(A-1)) + g(n-5*A) + 2A
     = O(n^2)

依此类推，可以得出结论 (n 5) 的计算步数增长的阶 为 O(n^5)

1.15
a) 12.15 连除 5次 3 小于 0.1 ，所以是 5次
b) 可以看出每调用一次 p 过程，需要递归1次 sine ，空间加1，计算步数加2，关键是p的次数：
   对于a，调用次数t，那么 a*3^(-t) < 0.1 , 即 10a < 3^t ==> lg(10a)/lg3 < t,
   所以增长阶 空间和时间 都为 O(log a)

posted on 2008-03-26 22:56 cuigang 阅读(1373) 评论(2)  编辑 收藏 引用 所属分类: Lisp/Scheme 、我的SICP答案

评论

# re: 我的SICP习题答案（1.14~1.15）  回复  更多评论   

1.14 题目中是 number of steps used by this process as the amount to be changed increases?
你上面的N是类别把，还是不对哦。。。。。。
以图上面节点数目为55
2008-07-21 20:12 | xiaokang

# re: 我的SICP习题答案（1.14~1.15）  回复  更多评论   

@xiaokang

n 是 钱数（美分）。
2008-08-03 15:13 | cuigang

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理