Zeitaufwand - O-Notation

[nath0x]

Hallo zusammen,

ich soll bei den folgenden zwei Aufgaben den Zeitaufwand, in der O-Notation bestimmen.

Aufgabe 1: Bestimme den Zeitaufwand zur Berechnung des größten gemeinsamen Teilers zweier Zahlen a und b für den schlimmsten und besten Fall. Dabei sei die Eingabekomplexität n := max{a, b}.

public int ggT(int a, int b) {
	while(a != b) {
		if (a > b) {
			a = a - b;
		} else {
			b = b - a;
		}
	}
}

Aufgabe 2: Bestimme den Zeitaufwand (in Abhängigkeit von n) des folgenden Programms:

int x = 3;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j += 3) {
	}
	x = x * 3;
}

Ich habe diesbezüglich natürlich schon hier recherchiert, was mich auch ein ganzes Stück weiter gebracht hat, jedoch blick ich bei dem Thema leider noch immer nicht so richtig durch (verstehe z.B. nicht so wirklich was mit 'Eingabekomplexität' gemeint sein soll).

Jedenfalls sind hier meine Herangehensweisen an die beiden Aufgaben (vermutlich vollkommen falsch):

zu Aufgabe 1:

Bester Fall:
O(1) * O(1) + O(1)
= O(1 * 1 + 1)
= O(1)

Schlechtester Fall:
O(n) * O(1) + O(1)
= O(n * 1 + 1)
= O(n)

zu Aufgabe 2:

O(n) + O(n) * O(n) * O(1)
= O(n * n * 1 + 1)
= O(n^2 + 1)
= O(n^2)

Es würde mich freuen, wenn sich jemand mal meine Lösungsansätze ansehen könnte und mir ggf. erklären könnte, was ich da falsch verstehe, bzw. wie man richtig an die obigen Aufgaben herangeht.

Vielen Dank schonmal!

 

[stg]

Die Ergebnisse stimmen, aber was du da "gerechnet" hast, erschließt sich mir nicht.

 

[nath0x]

Die Ergebnisse stimmen, aber was du da "gerechnet" hast, erschließt sich mir nicht.

Ok danke; das hab ich erwartet . Bin mir wie gesagt auch selbst ziemlich sicher, dass meine Herangehensweise an diese Aufgaben nicht ganz richtig ist.

Hier mal mein "Rechenweg" zu Aufgabe 2 in Kommentaren.

    int x = 3; //Wertzuweisung, entspricht Zeitaufwand O(1)
    for (int i = 0; i < n; i++) { //Schleife bis n, entspricht O(n)
        for (int j = 0; j < n; j += 3) { //Schleife bis n, entspricht O(n)
        }
        x = x * 3; //Wertzuweisung, entspricht O(1)
    }

//Der Gesamtaufwand entspricht demnach: O(1) + O(n) * O(n) * O(1)
// = O(1 + n * n * 1)
// = O(1 + n^2)
// = O(n^2)

Bei Aufgabe 1 ist die Schleife, die im besten Fall 1x (O(1)), oder im schlechtesten Fall n-mal (O(n)) durchläuft und dann kommt jeweils eine Bedingung (O(1)) und eine Wertzuweisung (O(1)).
Da ist dann entsprechend der Gesamtaufwand, nach dem obigen Prinzip (zusammenrechnen) = O(1) (best case) bzw. O(n) (worst case).

Hoffe das ist so jetzt einigermaßen nachvollziehbar.
Könntest du mir anhand des Beispiels erklären, wie das richtig zu machen ist, bzw. was ich offensichtlich falsch verstanden habe?

 

[Gucky]

Ist O(1*1+1) nicht O(2)?

 

[stg]

    int x = 3; //Wertzuweisung, entspricht Zeitaufwand O(1)
    for (int i = 0; i < n; i++) { //Schleife bis n, entspricht O(n)
        for (int j = 0; j < n; j += 3) { //Schleife bis n, entspricht O(n)
        }
        x = x * 3; //Wertzuweisung, entspricht O(1)
    }

//Der Gesamtaufwand entspricht demnach: O(1) + O(n) * O(n) * O(1)
// = O(1 + n * n * 1)
// = O(1 + n^2)
// = O(n^2)

Die zweite Wertzuweisung ist innerhalb der ersten, aber außerhalb der zweiten Schleife ( die zweite Schleife läuft sozusagen leer. Daher sollte es heißen

O(1) + O(n) * ( O(n) + O(1) )

Oder hast du dich hier beim abtippen vertippt?

Im Startpost hattest du dich offenbaur außerdem noch verschrieben, denn dort hattest du statt

O(1) + O(n) * O(n) * O(1)

gesagt

O(n) + O(n) * O(n) * O(1)

. Aufgrund zweier Fehler war es dann nicht wirklcih nachvollziehbar, ob du das Prinzip verstanden hast oder nicht.


Beim zweiten Aufgabenteil hast du dicht eventuell (ebenfalls?) vertippt und nicht den kompletten Code gepostet. So wie es dort steht ist das nämlich kein gültiger Java-Code. Wenn das allesdings auf den geposteten Code bezoegn wird, dann hast du im Bestbase (nämlich im Fall, dass

a=b

gilt, nur eine einzige Prüfung im Kopf der while-Schleife in O(1). Diese wird zu false ausgewertet und demnach gar nicht in die Schleife gesprungen. Was soll denn danach noch passieren?

Ist O(1*1+1) nicht O(2)?

Ja, aber O(2) = O(1). Und in der Praxis gibt man normalerweise nur O(1) an. Es geht hier im asymptotisches Laufzeitverhalten geschrieben in Landaunotation. Siehe dazu auch Landau-Symbole ? Wikipedia
Die Art und Weise, wie mit diesen Symbolen gerechnet wird, ist zwar mathematisch betrachtet absoluter Blödsinn und "fies anzuschauen", aber leider allgemein so üblich.

 

[Gucky]

Ach so. Wieder was gelernt. Danke

Nur aus Interesse: gibt es andere Notationen, bei denen sich ein Mathematiker nicht die Haare rauft und/oder die leichter zu verstehen sind?

 

[stg]

Nur aus Interesse: gibt es andere Notationen, bei denen sich ein Mathematiker nicht die Haare rauft und/oder die leichter zu verstehen sind?

Nichts, was wirklich geläufig ist. Jedenfalls ist mir da nichts bekannt. Man kann natürlich direkt mit der mathematschen Definition dieser Symbole arbeiten, aber man hat diese Abkürzungen ja genau deshalb eingeführt, damit man sich damit nicht herum schlagen muss.

Es ist auch nicht wirklich etwas daran auszusetzen, so etwas wie

O(n) + O(1) = O(n)

zu schreiben, sofern man sich im Klaren darüber ist, was damit denn tatsächlich gemeint ist. Streng genommen macht der +Operator an dieser Stelle nämlich überhaupt keinen Sinn, da es sich hier um Klassen von Funktionen handelt. Gemeint ist dann eigentlich so etwas wie:
Liegt eine Funktion f(n) in der Klasse O(n) und eine Funktion g(n) in O(1), dann liegt die Funktion (f+g)(n) in O(n). Oder kürzer:

f(n) ∈ O(n) ⋀ g(n) ∈ O(1) ⇒ (f+g)(n) ∈ O(n)

 

[nath0x]

Danke dir erstmal, ich glaube so langsam fang ich an das ganze zu verstehen.
Bezüglich eventueller Tippfehler etc. habe ich die beiden Code-Ausschnitte nochmal genau abgetippt und erneut versucht in die O-Notation zu 'übersetzen'.
(Dass die Aufgaben kein gültiger Java-Code sind (z.B. kein return-statement bei Aufgabe 1) stimmt. Sie sind aber definitiv so vorgegeben :S.

Aufgabe 1:
Bester Fall:

public int ggT(int a, int b) {
	while (a != b) { //Bedingung/Vergleich [entspricht O(1)]. Die Schleife wird nicht durchlaufen, da im besten Fall a = b.
		if (a > b) {
			a = a - b;
		} else {
			b = b - a;
		}
	}
}

//Gesamtaufwand: O(1)

Schlechtester Fall:

public int ggT(int a, int b) {
	while (a != b) { //Schleife läuft n-mal durch, bis die Bedingung erfüllt ist [entspricht O(n)].
		if (a > b) { //Bedingung [entspricht O(1)]
			a = a - b; //Wertzuweisung [entspricht O(1)]
		} else {
			b = b - a;
		}
	}
}

//Gesamtaufwand: O(n) * (O(1) + O(1))
/*Hier bin ich mir jetzt nicht sicher, ob bei der O-Notation die Klammer ausmultipliziert wird,
oder die Werte in den Klammern einfach zusammengefasst werden?

Sprich, Weg 1: (Klammer Ausmultiplizieren)
O(n) * (O(1) + O(1))
= O(n) * O(1) + O(n) * O(1)
= O(n * 1 + n * 1)
= O(n + n)
= O(n)

oder, Weg 2: (Klammer Zusammenfassen)
O(n) * (O(1) + O(1))
= O(n) * O(1)
= O(n * 1)
= O(n)
*/

Aufgabe 2:

int x = 3; //Wertzuweisung [entspricht O(1)]
for (int i = 0; i < n; i++) { //Schleife bis n [entspricht O(n)]
	for (int j = 0; j < n; j += 3) { //Schleife bis n [entspricht O(n)]
	}								 //Oder entspricht die Schleife hier O(n/3)? Da j jeweils um 3 erhöht wird?
	x = x * 3; //Wertzuweisung [entspricht O(1)]
}

//Gesamtaufwand: O(1) + O(n) * (O(n) + O(1))
/*Wieder die Frage ob Ausmultipliziert oder Zusammengefasst wird.

Weg 1: (Klammer ausmultiplizieren)
O(1) + O(n) * (O(n) + O(1))
= O(1) + O(n) * O(n) + O(n) * O(1)
= O(1 + n^2 + n * 1)
= O(1 + n^2 + n)
= O(n^2)

Weg 2: (Klammer zusammenfassen)
O(1) + O(n) * (O(n) + O(1))
= O(1) + O(n) * O(n)
= O(1 + n^2)
= O(n^2)
*/

Wie du siehst, sind beim Durchgehen der Aufgaben noch 2 kleine Fragen aufgekommen:
(angenommen alles andere ist soweit richtig)

1. Klammern ausmultiplizieren oder zusammenfassen?
2. Gilt bei der zweiten for-schleife in Aufgabe 2 O(n) oder O(n/3)?

Wär super, wenn du das noch klarstellen könntest.
Vielen Dank jedenfalls!

 

[stg]

1. Klammern ausmultiplizieren oder zusammenfassen?
2. Gilt bei der zweiten for-schleife in Aufgabe 2 O(n) oder O(n/3)?

Ich würde die Klammern "von innen nach außen" auflösen. Also immer erst das zusammenfassen, was innerhalb der Klammern steht und mich dann weiter nach außen arbeiten, da dann meiner Meinung nach klarer wird, was genau passiert. Streng genommen ist die ganze Notation aber Mist (siehe insbesondere mein Beitrag #7), jedoch wird das die Form sein, in der man die Lösung der Aufgabe von dir erwartet, also alles in Ordnung

Du hast richtig erkannt, dass du ungefähr nur n/3 Schleifendurchläufe hast. Die exakte Anzahl hängt nochmal davon ab, ob n durch drei teilbar ist oder nicht. Da bekommst du ohne da jetzt genau drüber nachzudenken evtl noch einen mehr oder weniger, aber das stört uns nicht. Ebenso wenig stört uns, dass wir nicht n sondern nur n/3 Schleifendurchläufe haben. Für jede beliebige Konstante c gilt nämlich

O(c·n) = O(n)

O(n) ist einfach die Klasse aller von n abhängigen Funktionen (Folgen, ...), die linear in n wachsen. Dabei ist es egal, ob etwa gilt f(n) = n, oder f(n) = 10000000000000000·n oder f(n) = 0,00000000000001·n, von Interesse ist dabei nur das asymptotische Wachstumsverhalten.

 

[nath0x]

Sehr schön erklärt. Ich denke, ich habe jetzt alles verstanden .
Da es den Thanks-button wohl nichtmehr gibt, hier nochmals vielen, vielen Dank für deine Hilfe!

 

[D4an1k]

Hallo,

hoffe das ich hier richtig bin.
Ich verstehe die O-Notation noch nicht ganz.

Folgendes Beispiel:

1:

s=0; //O(1)
for(i=0;i<k;i++){   //O(n)
    for(j=0;j<k;j++){   //O(n)
        s=s+brett[i][j];    //O(1)
    }
}

O(1) + O(n) * (O(n) + O(1))
= O(1) + O(n) * O(n) + O(n) * O(1)
= O(1 + n^2 + n * 1)
= O(1 + n^2 + n)
= O(n^2)

Die Musterlösung ist aber O(n).

Was habe ich übersehen bzw. falsch gemacht?

 

[Gucky]

Mach dafür bitte einen neuen Thread auf, anstatt einen von vor einem Jahr auszugraben.