Rekursive Funktionsanalyse

Question

Ich versuche, die Leistung eines rekursiven Programms zu analysieren, das ich geschrieben habe.

Der Grundcode ist

Cost(x) 
{ 
1 + MIN(Cost(x-1), Cost(x-2), Cost(x-3)) 
} 

ich eine Rekursion für die Anzahl der Anrufe auf Kosten() schreiben möchten. Wie würde ich das anfangen?

So etwas wie T(x) = T(x/2). Aber ich glaube nicht, dass das richtig ist

Edit: Ich kann dies als ein Baum mit einem Verzweigungsfaktor von 3 für jeden der 3 rekursiven Aufrufe von Cost() darstellen. Also wäre es genauer T(x) = T(x/3)?

Answer 1

Die Anzahl der getätigten Anrufe(), um zu Kosten wären:

C(x) = 1 + C(x-1) + C(x-2) + C(x-3) 

Also, für einen Eingang x, Kosten() wurde einmal zuzüglich der Höhe der Zeit nannte es für x-1 genannt wurde, x-2 und x-3. Dies setzt voraus, dass Ihre Lösung keine Memo-Erstellung verwendet. Die Rekursion ist nicht schön: http://www.wolframalpha.com/input/?i=T(x)+%3D+1+%2B+T(x-1)+%2B+T(x-2)+%2B+T(x-3)

memoization Verwendung jedoch Ihre „Anzahl der Anrufe“ wird C(x) = x, weil Sie nur C(i) einmal für alle i zwischen 0 und x bewerten müssen. (Könnte C(x) = x + 1 sein, abhängig von Ihren Anfangsbedingungen)

Answer 2

Sie haben wirklich eine rekursive Lösung schreiben (i seine eine Zuordnung Hoffnung gegen lineare Iteration zu vergleichen)

ich denke

T(X) = T(X-1)+T(X-2)+T(X-3)+C 
C is small constant