Laufzeit und O-Notation

[Mkhitaryan]

Sers

ich hätte da eine Frage bezüglich laufzeit und o-notationen. wie es ungefähr funktioniert, scheine ich kapiert zu haben, aber will nur noch mal sicher gehen.

Ich habe hier folgenden Codeausschnitte (ist aus einer früheren Klausur, wo es noch keine lösungen gibt und mehr ist nicht gegeben) und will daraus die laufzeitkomplexität berechnen:

		for ( int j = n-1; j>1; j--) { //wird n-2 mal durchlaufen
			
			for ( int i = 1; i<n ; i++) {  //wird n-1 mal durchlaufen
				
				array [j] = array [j] - 1;
				}
			}

Ist das Ergebnis dann O ( (n-1) (n-2) ) = O (n² - 3n + 2) ? Ich zweifle eigentlich nur daran, weil es ein ziemlich "unschönes" ergebnis ist :bloed:

Und zweitens, wie berechne ich sowas im Falle von if-else?

		if (x < 100) { //wird einmal durchlaufen
			y = x;
		} else
			for (int i = 1; i < n; i++) { //wird n-1 mal durchlaufen
				if (a[i] > y) //wird einmal durchlaufen
					y = a[i];
			}

Im besten fall ist das ja nur O(1), wenn x >= 100 ist. Oder muss ich hier sowas wie eine Fallunterscheidung machen oder nur den Worst-Case nehmen?
Für letzteres wäre es doch, wenn ich mich nicht irre, dann doch O (1 * (n-1) * 1) = O (n-1)

Sehe ich das alles so richtig oder habe ich irgendwo einen denkfehler gemacht?

Danke schon mal 🙂

 

[Klösp]

Ich lasse mich gerne korrigieren, aber soweit ich das in Erinnerung habe zählt nur die höchste Potenz.
Konstanteteile werden auf jeden Fall weggelassen, weil es um die Wachstumsklasse geht.

 

[rme]

Schau dir mal die Rechenregeln an, z.B. hier: Formelsammlung O-Notation ? Wedelwiki

Dort steht, und so habe ich es auch gelernt, dass für O(f(n) + g(n)) = max(O(f(n), O(g(n))) gilt. Das bedeutet, dass Summen in der Klasse ihrer größten (im Sinne der O-Notation) Summanden liegen. Also ist O(n² + n) = O(n²). Mit diesen Regeln kann man die Ausdrücke vereinfachen, in der entsprechenden Vorlesung werden diese Regeln üblicherweise auch bewiesen.

Zur Frage mit der Fallunterscheidung: Beim großen O gilt, dass der worst-case untersucht wird. Überleg dir also, wie für deinen Algorithmus der Worst-Case aussieht, d.h. in welchem Fall das äußerste if falsch ist und das innerste if am häufigsten wahr ist. Dann betrachtest du die Laufzeit dieser schlimmsten Eingabe.

 

[Mkhitaryan]

Okay, vielen Dank 🙂