Master theorem Verständnis

[blackpage]

Hallo,

ich hab en Problem beim aufstellen von T beim Master theorem.

Wenn ich beispielsweise folgenden code habe:

void g(int alpha, int omega){
int n = omega - alpha;
if (n <= 1){
return;
}
for (int i = 0; i < 4; ++i){
int ralpha = alpha + n * i / 6;
int romega = alpha + n * (i + 3) / 6;
g(ralpha, romega);
}
for (int j = alpha; j < omega; ++j){
for (int k = alpha; k < omega; ++k){
h(); //O(1)
}
}
}

die gleichung vom Mastertheorem lautet ja T = a*T(n/b) + f.

nur weiß ich jetzt gar nicht wie ich genau auf a komme. Habe viel recherchiert aber es wird mir nicht wirklich klar.

a soll laut meinem Buch die Anzahl der Aufrufe in der Rekursion darstellen.

Ich schätze diese finde ich in der ersten for schleife in meinem Beispielcode oben.

Aber handelt es sich da wirklich um 1 rekursiven aufruf nur oder muss man das anders zählen?

 

[blackpage]

und n müsste doch n=omega-alpha sein oder?

Ich blick da noch nicht so ganz durch :/


Würde mich über Hilfe freuen.

Vielen Dank!

 

[blackpage]

bitte hilft mir einer wenn er was weiß, ja?

 

[HonniCilest]

Aber handelt es sich da wirklich um 1 rekursiven aufruf nur oder muss man das anders zählen?

Ich denke man muss die Anzahl der Wiederholungen durch die for-Schleife nehmen, sprich a=4, denn rein theoretisch gesehen könntest du den Code ja auch mehrmals hintereinander schreiben, statt eine Schleife zu verwenden, es ist nur unsinnig aus programmiertechnischer Sicht...