Anzahl der Activation Records

Neue Frage »

Auf diesen Beitrag antworten »
marie m Anzahl der Activation Records

Hallo!!!

Wie kann ich die Anzahl der activation records einer rekursive Funktion finden?

Zum Beispiel bei diesen folgenden Pseudocode von BinarySearch.


code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
int BinarySearch(int A[1...n], int y, int low, int high) { 
 if (high < low) {
    return -1; //not found 
 }
 mid = low + (high - low) / 2; 
 if (A[mid] > y) {
    return BinarySearch(A, y, low, mid-1); 
 }
 else if (A[mid] < y) {
       return BinarySearch(A, y, mid+1, high); 
 }
 else {
      return mid; //found 
}
} 

 
Auf diesen Beitrag antworten »
marie m

Ich habe mir folgendes ueberlegt:
Am anfang gibt es ungefaer high-low Elements.
Dann high-(high-low)/2
Dann high-(high-(high-low)/2)/2
And so weiter...bis (high-low)/2^i=1 also i=log(high-low)

Ist das richtig?
Heisst das i mal deer algorithm us augefuehrt werden muss?

Also ist das die anzahl deer activation records?
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »