; ====================================================================== ; ; 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))
本文地址：http://com.8s8s.com/it/it23192.htm