Big-O-Notation: Wie groß ist der Aufwand für eine verschachtelte Schleife?

Hey kann mir jemand sagen wie ich für folgenden Code die BIG O Noation herausbekomme??

for(i=0;i<n;i++)
{
	for(j=0;j<n;j++)
	{
	    if(data[i] == data[j])
	    {	
		tue etwas
	    }
	}
}

Ansatz: Anzahl der Schleifendurchläufe
= (n-1) + (n-2) + (n-3) + .... + 2 + 1 (insgesamt n-1 Elemente)
= n*(n-1) + (-1 -2 -3 .... -(n-1))
wäre also O(n^2)

Aber ohne Gewähr.

Sowohl deine äußere als auch deine innere Schleife haben exakt n Durchläufe, also sind es insgesamt n^{2 Durchläufe (für jeden der n möglichen Werte von i, werden alle n Werte von j durchlaufen).
Wenn der Code innerhalb der zweiten Schleife nur konstante Laufzeit hat, also in O(1) liegt, ist somit deine gesamte Funktion in O(n}2).

@chilic: Es gibt keine Abhängigkeit zwischen den beiden Schleifen, also sind es exakt n^2 Schleifendurchläufe.

Danke erstmal! Was genau sagt mir jetzt n^2 kann ich damit auch die Zeit berechnen die mein programm für einen bestimmten wert für n benötigt?

Dir wurde doch im Prinzip in Dauer eines Schleifendurchlaufs berechnen schon gesagt, dass man das nicht genau vorhersagen und sich das von PC zu PC unterscheiden kann.

Oh ok da hab ich mich verguckt 😃
Ich dachte noch es ist Unsinn beide Schleifen von 0 an laufen zu lassen, da sonst immer ein Element mir sich selbst verglichen wird. Dann hab ich da wohl unbewusst noch mit reingebaut dass die innere Schleife auch erst ab i+1 loslaufen könnte, da sonst zwei Elemente immer zweimal verglichen werden.
Na aber so ists ja noch viel einfacher!

n^2 sagt dir dass die Laufzeit etwa quadratisch mit der Anzahl der Elemente zunimmt.
Berechnen kannst du da erst mal noch nichts, aber du kannst abschätzen was passiert wenn die Anzahl der Elemente sich ver-x-facht.

Was genau sagt mir jetzt n^2

Siehe: Landau-Symbole und besonders die Diagramme in A brief intro to algorithmic time complexity.

Hallo snsewill,

der Gesamtaufwand hängt natürlich auch von tue was ab. Wenn der Aufwand dafür konstant ist, also O(1), dann kommt für den Algorithmus insgesamt O(n^{2) raus, egal wie oft die Bedingung erfüllt ist. Ist der Aufwand höher, hängt es davon ab, wie oft die Bedingung erfüllt ist. Ist die Bedingung z.B. im Schnitt bei jedem 10 Durchlauf erfüllt und ist der Aufwand für tue was z.B. O(n) ist, dann wäre der Gesamtaufwand O(n}3).

Die Aufwandsklasse sagt - wie schon von Abt gesagt - nichts darüber aus, wie schnell die Ausführung auf einem bestimmten Computer ist. Das liegt vor allem daran, das O(c*x) = O(x) für jedes konstante c und jedes beliebige x. Konstante Faktoren werden bei der O-Notation also einfach ignoriert. Für die tatsächliche Laufzeit spielen die konstanten Faktoren natürlich eine Rolle.

Die O-Notation ist vor allem dafür da abzuschätzen, wie sich die Laufzeit entwickelt, wenn die Eingabelänge wächst. Bei O(n^2) vervierfacht sich der Aufwand, wenn sich die Eingabelänge verdoppelt. Das kann auch bei heutigen Computern bei längeren Listen durchaus ein Problem werden. Gerade wenn der konstante Faktor hoch ist.

Alle Elemente mit allen Elementen vergleichen sollte man daher nach Möglichkeit vermeiden. Wenn man z.B. doppelte Elemente finden will und eine Ordnung auf den Elementen definiert ist, dann ist es z.B. besser, die Liste zu sortieren. Anschließend kann man die Liste einmal durchlaufen und muss nur noch schauen, ob die direkt benachbarten Elemente gleich sind. Der Aufwand dafür ist unter Verwendung Quicksort für quasi alle praktisch vorkommenden Fälle O(n*log(n)).

Mit noch geringerem Aufwand funktioniert eine Prüfung auf Duplikate, indem mal alle Elemente einem HashSet hinzufügt. Am Rückgabewert von Add sieht man, ob das Element schon vorhanden war. Das hat - eine geeignete Hashfunktion vorausgesetzt - für quasi alle praktischen Fälle einen Aufwand von O(n).

Jetzt habe ich viel geschrieben, ärgern tue ich mich trotzdem. Dieses Thread ist quasi ein Crosspost zu deinem früheren, wenn auch mit einem leicht anderen Fokus. Wenn man das Thema noch etwas weiterfasst, nämlich "Effizienz von Schleifen im weiteren Sinne", dann gibt es schon vier Threads von dir dazu. Wir helfen grundsätzlich gerne, aber irgendwann muss es auch mal gut sein.

herbivore