sicp 1.15习题解答

    本小节主要介绍了阶的概念，与算法中计算时间和空间复杂度类似。给了一个过程：

<!---->(define (cube x)(* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
         (if (not (> (abs angle) 0.1))
             angle
             (p (sine (/ angle 3.0)))))

    这个过程用于求弧度的正弦值
a)在求值(sine 12.15)时，p过程将被使用多少次？
答：
(sine 12.15)->(p (sine 4.05))
            ->(p (p (sine 1.35)))
            ->(p (p (p (sine 0.45))))
            ->(p (p (p (p (sine 0.15)))))
            ->(p (p (p (p (p (sine 0.05))))))
显而易见，p被调用了5次

b)由过程sine所产生的计算过程使用的空间和步数增长的阶是多少？
从上面的分析可以看出，空间和步数的增长都跟p的调用次数成正比，也就是与递归次数是线性关系。
当|a|<0.1时，递归次数为0
当|a|>0.1时，递归的最大次数满足条件：|a|/3**num<0.1，这里的3**num采用ruby记法表示3的num次方，此时递归次数num<log3(10a)
因此，对于空间和步数的阶应该为:R(n)=(theta)lg(n)

dennis 2007-05-10 14:58 发表评论