; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 02/27/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.1.15
;; 本题为理解题
;; a.
;; (sine 12.15) ==> p (sine 4.5)
;; ==> p (p (sine 1.5))
;; ==> p (p (p (sine 0.5)))
;; ==> p (p (p (p (sine 0.16666666))))
;; ==> p (p (p (p (p (sine 0.0555555555))))
;; 所以共调用5次p
;; b.
;; 在计算(sine a)时，每多一层递归调用sine，均会多占用定长的keep trace空间和定量
;; 的数值比较运算及p函数的数值计算时间，其他因素占用均为常数级[theta](1)。因此空间
;; 复杂度s(a)和时间复杂度t(a)均与递归次数c成线性关系，c为使(|a|/(3^c))<0.1成立的最
;; 小非负整数，所以c=log3(10a) 当|a|>0.1 c=0当|a|<=0.1
;; 所以s(a)= t(a) = [theta](ln(a))
|
本类阅读TOP10