sicp习题试解 (1.15)

; ======================================================================

;

; 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))