Zeitkomplexität für das Count-Change-Verfahren in SICP

Question

In der berühmten Struktur und Interpretation von Computerprogrammen gibt es eine Übung (1.14), das nach der zeitlichen Komplexität des folgenden Algorithmus – in Scheme – zum Zählen von Änderungen fragt (die Problemstellung schlägt vor, den Baum für zu zeichnen). (cc 11 5) - was aussieht so was):

 ; count change
 (define (count-change amount)
   (define (cc amount kinds-of-coins)
     (cond ((= amount 0) 1)
           ((or (< amount 0) (= kinds-of-coins 0)) 0)
           (else (+ (cc (- amount
                           (first-denomination kinds-of-coins))
                        kinds-of-coins)
                    (cc amount
                        (- kinds-of-coins 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)))
   (cc amount 5))

Jetzt...Es gibt Websites mit Lösungen für die SICP-Probleme, aber ich konnte keinen leicht verständlichen Beweis dafür finden Zeit Komplexität des Algorithmus – irgendwo wird erwähnt, dass es sich um ein Polynom handelt O(n^5)

Answer 1

Wahrscheinlich war dies nicht der richtige Ort für diese Frage, aber trotzdem fand ich die Antwort in der Zwischenzeit in Form eines meist "verdaulichen" Beweiss bei http://wqzhang.wordpress.com/2009/06/09/sicp-exercise-14/.

Answer 2

Reihenfolge des Wachstums der Schrittzahl:$ heta (n^5)$

Wir können beweisen, dass die Wachstumsordnung der Anzahl der Schritte im Allgemeinen $ heta (n^m)$ ist, wobei $m$ die Anzahl der verfügbaren Münztypen ist.Hier ist meine (sehr) grobe Argumentation mittels Induktion:

1. Wenn es nur eine Münzsorte gibt, ist die Anzahl der Schritte offensichtlich proportional zu n.

2. Angenommen, es würde dauern (cc n m) Schritte zum Ändern eines Betrags von $n$ mit $m$-Münztypen.Lassen Sie uns nun überlegen (cc n m+1):($A$ ist der Nennwert der $m$-ten Münzsorte.)

(cc $n$ $m+1$)
= (cc $n$ $m$) + (cc $n-A$ $m+1$)
= (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m+1$)
= (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m$) + (cc $n-3A$ $m+1$)
= ......

Es würde sich irgendwann ergeben

(cc n m) + (cc n-A m) + ... + (cc <something-negative> m+1)

Es gibt ungefähr $n/A$ Artikel.Die Gesamtzahl der Schritte wäre also proportional zu $n/A*n^m$, was wiederum proportional zu $n^{m+1}$ ist.Somit ist die Reihenfolge des Wachstums für die Anzahl der Schritte von (cc n m) ist $ heta (n^m)$.

Sei $m$ 5 und die Reihenfolge des Wachstums der Anzahl der Schritte ist $ heta (n^5)$.