Posted on 2007-05-10 14:58
dennis 閱讀(747)
評論(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)