Laufzeitkomplexität in der O-Notation

[the snake II]

Ich brauche Hilfe bei folgender Übungsaufgabe:


Bestimmen Sie die Laufzeitkomplexität der folgenden Funktion bar nur in Abhängigkeit von der Eingabegröße n in Form der O-Notation, wenn die Funktion foo(i,j,n) bei jedem aufruf 2^j Schritte braucht. Betrachten Sie m als Konstante.

Tipp:

int bar (int m, int n) {
	int i, j;
	for (i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
		{
			foo(i,j,n);
		} 
	}
}

Die Anzahl der Durchläufe der äußeren for-Schleife ist unabhängig von der Eingabegröße. Also O(1)...?
Die Anzahl der Durchläufe der inneren Schleife ist proportional zu n. Also O...?
Das Ergebnis ist dann: O(1) * O * ?

Was zeigt mir der Tipp? Und wie rechne ich alles zusammen?


Mit vielem Dank im Vorraus,

André

 

[Matthias Reitinger]

Hallo André,

deine bisherige Analyse sieht mir schon korrekt aus. O(1) Durchläufe der äußeren Schleife, O Durchläufe der inneren Schleife. Die innere Schleife benötigt pro Durchlauf 2^j Schritte, wobei j der Schleifenzähler ist. j nimmt nacheinander die Werte 0, 1, …, n-1 an. Insgesamt benötigen alle Aufrufe von foo also ?_j=0^n-1 2^j Schritte. Mit dem gegebenen Tipp solltest du den Rest schaffen.

Grüße,
Matthias

 

[the snake II]

Hallo Matthias,

vielen Dank für Deine Antwort.
Der folgende Lösungsversuch ist geraten:

O(1)*O*O(2ⁿ) = O(2ⁿ)

Richtig?

 

[Matthias Reitinger]

Hallo André,

deine Rechnung kann so nicht stimmen. Du kannst das O in deinem Ansatz nicht einfach unter den Tisch fallen lassen. O(n*2ⁿ) ? O(2ⁿ)!

Ich hab dir die Summe der Schritte in der inneren Schleife doch schon hingeschrieben. Die müsstest du jetzt (mit dem gegebenen Tipp) nur noch umformen und dann argumentieren, wieso das dann asymptotisch schon die Gesamtanzahl der Schritte ist.

Grüße,
Matthias