SICP 1.2.3

Posted on 2015-02-12 20:42:17 +0900 in SICP Lisp

Time and space complexity is kind of difficult for me.

1.14

 (define (count-change amount) 
   (cc amount 5)) 
 (define (cc amount kinds-of-coins) 
   (cond ((= amount 0) 1) 
         ((or (< amount 0) (= kinds-of-coins 0)) 0) 
         (else (+ (cc amount 
                      (- kinds-of-coins 1)) 
                  (cc (- amount 
                         (first-denomination kinds-of-coins)) 
                      kinds-of-coins))))) 
 (define (first-denomination kinds-of-coins) 
   (cond ((= kinds-of-coins 1) 50) 
         ((= kinds-of-coins 2) 25) 
         ((= kinds-of-coins 3) 10) 
         ((= kinds-of-coins 4) 5) 
         ((= kinds-of-coins 5) 1)))

To analyze the time complexity of $cc(n, k)$, it is more easy to start from $k=1$

if $k=1$, then $cc(n, 1)=O(n)$

if $k=2$, then $cc(n, 2) = cc(n - 5, 2) + cc(n, 1) = O(n^2)$

…

By induction, $cc(n, 5)=O(n^5)$

1.15

Time complexity is about $log_3(n)$.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | SICP 1.2.2 »

Hide Comments

comments powered by Disqus