Wie berechnet man die Anzahl der Knoten in einem Baum gegebenen Algorithmus?

Question

Ich habe ein Problem, mit dem ich Hilfe brauche. Im geben:

int sum(int[] array, int first, int last) 
{ 
if (first == last) 
return array[first]; 
int mid = (first + last)/2; 
return sum(array, first, mid) + sum(array, mid + 1, last); 
} 

Frage: Bestimmen Sie eine Formel, die die Anzahl der Knoten im Rekursionsbaum zählt.

So habe ich die Rekursionsgleichung: T (n) = 2T (n/2) + dn

und beispielsweise für eine Anordnung der Länge 8, die Anzahl der Knoten in dem Rekursionsbaum würde 15 sein , die anzeigen würde, dass die Anzahl der Knoten in einem Baum 2n-1 wäre, wobei n die Größe des Arrays ist.

Ich habe mich gefragt, ob mein Denken korrekt ist und kann die 2n-1 Formel auf jeden Fall angewendet werden? Gibt es eine allgemeine Möglichkeit, die Anzahl der Knoten in einem Rekursionsbaum bei einem rekursiven Algorithmus zu berechnen?

Vielen Dank für Ihre Hilfe!

Answer 1

 2 
    /\ 
    1 1 // 2(n) - 1 = 2(2) - 1 = 3 seems to match! 

     3 
    /\ 
    2 1 
/\ 
    1 1  // 2(n) - 1 = 2(3) - 1 = 5 which seems to match 

Aus ein paar anderen Beispielen geht hervor, dass die Formel 2 (n) - 1 korrekt zu sein scheint.