sicp 练习1.14 (2) 计算步数增长的阶(时间复杂度)

1.14_1.scm

(define (count-change amount)
    (cc amount 5 0)
)

(define (cc amount kinds-of-coins depth)
    (define from-node (cc-node-depth amount kinds-of-coins depth))
    (display (cc-node-depth-label amount kinds-of-coins depth))
    (cond 
            ((= amount 0) 1) 
            ((or (< amount 0) (= kinds-of-coins 0)) 0)
            (else   (let ((to-node (cc-node-depth amount (- kinds-of-coins 1) (+ depth 1)))) (display (cc-link from-node to-node)))
                    (let ((to-node (cc-node-depth (- amount (first-denomination kinds-of-coins)) kinds-of-coins (+ depth 1)))) (display (cc-link from-node to-node)))
                    (+  
                      ;除第一种硬币之外的所有其他硬币的不同方式的数目.
                      (cc amount (- kinds-of-coins 1) (+ depth 1)) 

                      ; 将现金 a - d 换成所有种类的硬币的不同方式的数目. 
                      (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins (+ depth 1))
                   )
            )
    )
)

(define (first-denomination kinds-of-coins)
    (cond
        ((= kinds-of-coins 1) 1) 
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)
    )
)

(define (cc-node amount kinds-of-coins)
    ; (cc 11 5)
    (string-append "(cc " (number->string amount) " " (number->string kinds-of-coins) ")")
)

(define (cc-node-depth amount kinds-of-coins depth)
    (define node (cc-node amount kinds-of-coins))
    
    ; "[0] (cc 11 5)"
    (string-append "\"[" (number->string depth) "] " node "\"")
)

(define (cc-node-depth-label amount kinds-of-coins depth)
    (define node (cc-node amount kinds-of-coins))
    (define color 
        (cond ((= amount 0) "gray80")
              ((= kinds-of-coins 1) "lightblue")
              ((= kinds-of-coins 2) "green")
              ((= kinds-of-coins 3) "firebrick1")
              ((= kinds-of-coins 4) "chocolate2")
              ((= kinds-of-coins 5) "magenta3")
              (else "gray95")
        )
    )

    (string-append "\"[" (number->string depth) "] " node "\" [label=\"" node "\",color=" color "];\n")
)

(define (cc-link from-node to-node)
    ; "[0] (cc 11 5)" -> "[1] (cc 11 4)"; 
    (string-append from-node " ->  " to-node ";\n")
)

依然是参考 https://codology.net/post/sicp-solution-exercise-1-14/

后半部分, 关于 时间复杂度的推演, 让我很受触动.

基于 简单的 从特殊到一般, 从低阶(T(n, 1)) 到 高阶(T(n,5)) 的 递进计算, 辅以 基础的数学知识, 就可以准确计算出 精确的 "计算步骤数".

我原来一直以为 "复杂度" 的计算, 必然都是 非常 高超的 "算法" 计算技巧, 竟然, 也都是 逐步推导出来的.

以后遇到 特殊的 实际的 算法复杂度 对比问题, 我也要试着 实际尝试推导分析下, 而不是简单地 凭直觉 "猜".

附上 (cc 12 2) 对应的图形, 供后续查阅: