Video anzeigen
zur Videoseite: O-Notation
Wichtige Inhalte in diesem Video
Was ist eigentlich die O-Notation und wozu brauchst du die? Diese Fragen beantworten wir dir hier im Beitrag und in unserem Video.
Inhaltsübersicht
O-Notation einfach erklärt
im Videozur Stelle im Video springen
(00:14)
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.
Beispiel für Laufzeitvergleiche
Die O-Notation kannst du beispielsweise verwenden, um Sortieralgorithmen miteinander zu vergleichen.Wenn du eine große Menge an Zahlen sortieren musst, ist es natürlich besser einen schnelleren Algorithmus zu wählen. Bubblesort oder Selectionsort haben im worst case zum Beispiel eine langsamere Laufzeit als Mergesort.
Komplexitätsklassen
Mit der O-Notation werden Algorithmen in verschiedene Komplexitätsklasseneingeordnet. 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:
O-Notation | Erklärung | Beispiele |
O(1) | Die Laufzeit des Algorithmusist konstant. |
|
O(log n) | Die Laufzeit ist logarithmisch. Wenn sich n verdoppelt, wächst die Laufzeit um einen konstanten Betrag. | binäre Suche in einer sortierten Menge – die Menge wird halbiert, bis das gesuchte Element gefunden wurde |
O(n) | Die Laufzeit ist linear. Wenn sich das n verdoppelt, verdoppelt sich auch die Laufzeit. | bis das Element gefunden wurde, durchsucht der Algorithmuseine Menge und betrachtet jedes Element nacheinander |
O(nlogn) | Die Laufzeit ist Super-Linear (logarithmisch Linear). Dabei steigt die Laufzeit etwas stärker an als linear. | Sortieralgorithmen wie Heapsort oder Mergesort |
O(n2) | Die Laufzeit ist quadratisch:Wenn sich zum Beispiel das n verdoppelt, vervierfacht sich die Laufzeit. | Sortieralgorithmen wie Bubblesort oder Selectionsort |
O(2n) | Die Laufzeit ist exponentiell:Wenn n sich um eins erhöht, verdoppelt sich die Laufzeit. | Bilden aller Paare in einer Menge |
O(n!) | Die Laufzeit erhöht sich faktoriell: Wächst n um 1, wird die Laufzeit um n+1 mal größer. | das Problem des Handelsreisenden (Travelling Salesman Problem) |
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(2n) 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
im Videozur Stelle im Video springen
(03:19)
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 naber sehr groß wird, erkennst du, wie wichtig ein schneller Algorithmus ist.
Sieh dir dazu die folgenden zwei Laufzeiten an:
100 • log n
0,001 • n2
Wenn jetzt n = 100 genommen wird, ist zunächst die untere Laufzeit insgesamt kürzer:
100 • log(100) = 200
0,001 • 1002 = 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 • 10002 = 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:
20n2 + 7n + 12.389
ist für dich also nur die n2 wirklich wichtig. In der O-Notation schreibst du also: O(n2).
O-Notation Beispiel
im Videozur Stelle im Video springen
(03:51)
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-1] do 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. Ertrifft 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 = n2. In der O-Notation ist das dann: O(n2).
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 Θ(n2). 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 brauchtder 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 verschiedenenSortieralgorithmen und ihre Laufzeiten haben willst, dann schau doch mal hier vorbei.
Beliebte Inhalte aus dem BereichTheoretische Informatik
- Reelle Zahlen - Exzeß-q und FestkommaDauer:04:53
- Reelle Zahlen - GleitkommaDauer:03:24
Weitere Inhalte:Theoretische Informatik
Zahlen in der Informatik
