Posted on 2007-05-10 14:58
dennis 阅读(718)
评论(0) 编辑 收藏 所属分类:
计算机科学与基础
本小节主要介绍了阶的概念，与算法中计算时间和空间复杂度类似。给了一个过程：
(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)