O-Notation

O-Notation einfach erklärt

In der Informatik stellt sich dir häufig die Frage: Wie gut ist ein Algorithmus eigentlich? Um das herauszufinden, wird oft eine Laufzeitanalyse gemacht. Mit der O-Notation (engl. Big O Notation) machst du dann die Laufzeit oder auch die Größe von Algorithmen vergleichbar. Denn sie ordnet die Laufzeiten Komplexitätsklassen ein.

Dabei beschreibt die O-Notation, wie langsam der Algorithmus im schlimmsten Fall (engl. worst case) ist. 

Gut zu wissen: Du nennst die Symbole der O-Notation auch Landau-Symbole. 

Komplexitätsklassen

Mit der O-Notation werden Algorithmen in verschiedene Komplexitätsklassen eingeordnet. Du siehst dir die Algorithmen dabei immer in Abhängigkeit ihrer Eingabegröße n an. Dabei beschreibst du jede Klasse mit dem sogenannten Landau-Symbol „O“. Hier ist eine Übersicht: 

Die Laufzeitunterschiede bei den wichtigsten Komplexitätsklassen erkennst du ganz deutlich in dem Graphen. Wie du sehen kannst, werden sie mit höherer Komplexität auch immer steiler. Das bedeutet, dass sich die Laufzeit des Algorithmus mit höherem n auch immer stärker erhöht.

direkt ins Video springen

O(2ⁿ) und O(n!) würden überhaupt nicht mehr auf den Graphen draufpassen. Algorithmen mit einer so hohen Komplexität sind sehr ineffizient. 

O-Notation berechnen

Bei zum Beispiel einer geringen Menge an Zahlen, die du sortieren willst, fallen die Unterschiede in der Laufzeit von verschiedenen Algorithmen gar nicht so wirklich auf. Wenn die Eingabegröße n aber sehr groß wird, erkennst du, wie wichtig ein schneller Algorithmus ist.

Sieh dir dazu die folgenden zwei Laufzeiten an:

100 • log n
0,001 • n²

Wenn jetzt n = 100 genommen wird, ist zunächst die untere Laufzeit insgesamt kürzer:

100 • log(100) = 200
0,001 • 100² = 10

Bei höheren Zahlen für n wie zum Beispiel n = 1000 siehst du aber schnell, dass die untere Laufzeit viel länger wird:

100 • log(1000) = 300
0,001 • 1000² = 1000

Wenn du eine Laufzeit betrachtest, musst du für die O-Notation immer nur auf den am stärksten wachsenden Summanden achten. Alle anderen Summanden oder Konstanten werden bei sehr hohen n nämlich irgendwann irrelevant.

Bei einer Laufzeit, die so aussieht:

20n² + 7n + 12.389

ist für dich also nur die n² wirklich wichtig. In der O-Notation schreibst du also: O(n²).

O-Notation Beispiel

Schauen wir uns die O-Notation doch mal am Beispiel vom Sortieralgorithmus Insertionsort an. Wir benutzen den Algorithmus, um ein Array mit n Zahlen zu sortieren. Der Algorithmus funktioniert dabei so: 

Insertionsort sortiert das Array so, wie du wahrscheinlich Spielkarten nach Wert sortierst. Angenommen, du hast auf deiner Hand bereits eine Kreuz 5 und eine Kreuz 9. Wenn du jetzt die Kreuz 7 einsortieren willst, ordnest du sie in die Mitte der beiden anderen Karten ein. So macht das auch Insertionsort mit Zahlen. 

Hier ist der Pseudocode für Insertionsort:

Insertionsort (Liste l)
  for a in 0 -> l.length – 2
  do
      b = a + 1
      tmp = l[b]
      while b > 0 AND tmp 
          l[b] = l[b-1]
          b – –
      l[b] = tmp

Übrigens: Wenn du genau wissen willst, wie Insertionsort funktioniert, haben wir hier einen Beitrag dazu für dich!

Für die O-Notation wird jetzt der schlimmste Fall für den Algorithmus überprüft, also der Fall, für den Insertionsort am längsten braucht. Er trifft hier ein, wenn das Array beispielsweise absteigend sortiert ist und jetzt aufsteigend sortiert werden soll. Der Algorithmus muss für jedes einzusortierende Element also jedes bereits einsortierte Element überprüfen.

Bei einem Array von n muss jedes Element sowohl durch die For-Schleife, als auch durch die verschachtelte While-Schleife. Dadurch ist also die Laufzeit n • n = n². In der O-Notation ist das dann: O(n²). 

Average Case und Best Case

Du kannst bei einem Algorithmus wie Insertionsort aber nicht nur den „worst case“ betrachten. Es gibt auch noch den „average case“ und den „best case“. Dabei betrachtest du jeweils die Laufzeit eines durchschnittlichen und des bestmöglichen Sortiervorgangs.

Du verwendest die gleichen Komplexitätsgrößen wie bei der O-Notation, aber nimmst für den Durchschnitt die Θ-Notation (Theta-Notation) und für den besten Durchlauf die Ω-Notation (Omega-Notation). Das sind einfach nur andere Symbole als bei der O-Notation. Alle drei sind Teil der Landau Notation. 

Bei Insertionsort ist der average case auch quadratisch, also Θ(n²). Der best case hingegen ist ein bereits sortiertes Array. Damit verkürzt sich die Laufzeit und wird linear: Ω(n). 

Zeit- und Platzkomplexität

Mit der O-Notation kannst du zwei verschiedene Arten der Komplexität untersuchen. 

Bei der Zeitkomplexität beschreibst du die Laufzeit eines Algorithmus in Abhängigkeit der Eingabegröße. Du stellst dir die Frage: „Um wie viel verlangsamt sich ein Algorithmus, wenn es mehr Eingabedaten gibt?“. 

Bei der Platzkomplexität beschreibst du hingegen, wie viel Platz der Algorithmus einnimmt in Abhängigkeit der Eingabegröße. Hier fragst du dich: „Wie viel zusätzlichen Speicher braucht der Algorithmus bei der Ausführung, wenn es mehr Eingabedaten gibt?“. 

O-Notation — häufigste Fragen

• Was bedeutet O(1)? 
  O(1) ist eine konstante Laufzeit eines Algorithmus. Das O steht dabei für die O-Notation. Ein Algorithmus mit einer konstanten Laufzeit wird meist nur einmal durchlaufen und ist dadurch im Vergleich sehr schnell. 
    
• Wie funktioniert die O-Notation? 
  Bei der O-Notation wird die Laufzeit eines Algorithmus in Abhängigkeit einer Eingabegröße dargestellt. Dadurch kannst du verschiedene Algorithmen miteinander vergleichbar machen. 

Sortieralgorithmen

Jetzt weißt du, was die O-Notation in der Informatik ist. Sie spielt besonders bei Sortieralgorithmen eine wichtige Rolle. Wenn du einen Überblick über die verschiedenen Sortieralgorithmen und ihre Laufzeiten haben willst, dann schau doch mal hier vorbei.