Einfach gesagt zählst die Anzahl der verschachtelten Schleifendurchläufe
O(n) sieht z.B. so aus
while(i < myArray.size()) {
doSomethingAwesome(myArray);
i++;
}
Wohingegen O(n²) so aussehen würde
while(i < myArray.size()) {
while(j < myArray.size()) {
doSomethingAwesome(myArray);
j++;
}
i++;
}
Denn die Funktion doSomethingAwesome() wird für jedes i genau j mal ausgeführt, also i*j. Beide schleifen sind abhängig von der Größe der Eingabedaten (myArray). Die O-Notation bezeichnet die Eingabedaten mit n. Wenn du jetzt eine Arraygröße von 10 hast, wird die doSomethingAwesome() Funktion im ersten Beispiel 10 mal aufgerufen. Im zweiten Beispiel allerdings bereits 100 mal!
Mit der O-Notation will man prinzipiell ausdrücken wie stark der Rechenaufwand mit dem Wachstum der Eingabedaten steigt. Das ist wichtig um herauszufinden wie der Code skaliert. Also wenn man z.B. ein Spiel hat, möchte man wissen ob wenn 1 Server für 10 Spieler reicht, man für 20 Speicher 2 Server wie bei O(n) oder 4 Server wie bei O(n²) braucht.
Vorsichtig musst du sein wenn du das Array pro Schleifendurchlauf verkleinern kannst. Dann bringst du nämlich den Faktor log(n) rein. Nehmen wir an du hast ein aufsteigend sortiertes Array von Zahlen und du suchst das Element mit einer bestimmten Zahl, z.B. um zu prüfen ob diese enthalten ist. Dann könntest du so vorgehen.
int i = myArray.size();
while(myArray[i] != myFavoriteNumber) {
if(myArray[i/2] < myFavoriteNumber) {
i = i/2;
} else {
i = i/2 + i/4;
}
}
Damit teilst du den Suchraum pro Schleifendurchlauf in die Hälfte.
Das absolut schlimmste ist wenn du exponenzielle Laufzeit hast, also O(x^n). X ist dabei eine konstante, oder auch n, egal, in jedem Fall schlimm weil die Reichenzeit extrem schnell ansteigt.
Außerdem gibt es noch O(1). Konstante Laufzeit. Das hast du wie Rechenzeit gar nicht von der Größe der Eingabedaten abhängt.
Noch zu erwähnen sei das immer in Best-Case, Worst-Case und Average-Case. Bei einer Suche kann es z.B. sein das der Best-Case O(1) ist, weil im bestenfall das erste untersuchte Element dem gesuchten Element entspricht und im Worst-Case O(n) ist, weil es das letzte untersuchte Element ist.
Die Codebeispiele sind alle iterativ, sehr simpel, unvollständig und nicht auf lauffähigkeit geprüft. Wenn du rekursive Programmierung verstanden hast, wirst du aber kein Problem haben auf Rekursion umzuschreiben.
Wenn man das ganze weiter verfolgt endet man übrigens irgendwann in der Theoretischen Informatik bei den Komplexitätsklassen P, NP, NP-Hart und NP-Vollständig. Das muss dich aber jetzt nicht kümmern, nur das du es vielleicht irgendwann zuordnen kannst ;)