; ====================================================================== ; ; Structure and Interpretation of Computer Programs ; (trial answer to excercises) ; ; 计算机程序的构造和解释(习题试解) ; ; created: code17 02/28/05 ; modified: ; (保持内容完整不变前提下,可以任意转载) ; ======================================================================
;; SICP No.1.26 ;; 本题为理解题
;; 在Louis的程序中(* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) ;; 会显式地调用(expmod base (/exp 2) m)两次,也就是说进行两次重复的计算, ;; 而不是像原程序中的一次,所以时间复杂度一定会大大增加。
;; 如果原程序中的时间复杂度可表示为 ;; t(n) = c + t(n/2) ==> t(n) = c * log2(n) = [theta](log(n)) ;; 则Louis的程序中的时间复杂度为 ;; t(n) = c + 2 * t(n/2) ==> t(n) = c * 2^(log2(n)+1) = 2c * n = [theta](n) ;; (此处使用公式1+2+4+8+...2^k = 2^(k+1))

|