Stelle Dir vor, Du programmierst einen Sortieralgorithmus für das Inventar in einem Online-RPG. Dieser soll die Gegenstände im Handumdrehen sortieren, egal wie voll und durcheinander das Inventar des Spielers ist.
Doch wie stellst Du sicher, dass Dein Algorithmus immer schnell genug ist? Hier kommt die O-Notation ins Spiel! Du kannst damit die Performance Deines Algorithmus abschätzen und den für Dich richtigen wählen.
O-Notation – Informatik
Die O-Notation (englisch: Big O notation) ist eine Methode in der Informatik, um den Aufwand von Algorithmen bzw. die Komplexität von Funktionen in Abhängigkeit ihrer Eingabegröße einzuordnen. Sie macht dadurch die Effizienz von Algorithmen vergleichbar.
Jede Algorithmus-Ausführung benötigt einen bestimmten Aufwand an Rechenzeit, die Laufzeit. Die Angabe der Laufzeit könnte zum Beispiel in Millisekunden erfolgen.
Diese Messung hätte allerdings nur wenig allgemeine Aussagekraft. Die Laufzeit variiert logischerweise, je nachdem welche Hardware man benutzt und wie groß man die Eingabemenge für den Algorithmus wählt.
Die O-Notation aber soll die Algorithmen in ihrer Laufzeit vergleichbar machen und stellt daher keine genaue Berechnung des Aufwands dar. Stattdessen ordnet sie Algorithmen und Funktionen in Komplexitätsklassen ein.
Alternativ wird die O-Notation auch asymptotische Notation genannt und gehört zur Bachmann-Landau-Notation.
O-Notation einfach erklärt
Bei der O-Notation ist primär die Betrachtung hoher Eingabegrößen relevant. Die simple Frage dabei: Wie stark und wie schnell verändert sich die Algorithmus-Laufzeit, wenn die Eingabegröße wächst?
Stell Dir vor, Du hast eine Liste mit x Elementen, und willst ein bestimmtes Element finden. Dazu erhältst Du zwei Suchalgorithmen, die diese Aufgabe erledigen.
Bei zehn Elementen in der Liste wird die Laufzeit beider Algorithmen ähnlich ausfallen. Aber was ist, wenn die Liste eine Million oder gar eine Milliarde Elemente enthält?
Bei diesen Größen kann sich die Laufzeit der Algorithmen um Jahre unterscheiden!
Die O-Notation beschreibt die obere Komplexitätsgrenze eines Algorithmus, also wie langsam dieser im schlimmsten Fall werden kann.
Bei einer linearen Suche in einer Liste, das heißt einer Suche Element für Element von vorn bis hinten, wäre das Worst Case Szenario, wenn das gesuchte Element ganz am Ende der Liste steht. In diesem Fall müsste die gesamte Liste durchlaufen werden.
Meist verwendet man die O-Notation für die Beschreibung der Zeitkomplexität eines Algorithmus. Man kann mit der Notation jedoch auch die Platzkomplexität beschreiben, das heißt die Frage: Wie viel mehr Speicherplatz benötigt ein Algorithmus, wenn seine Eingabegröße wächst?
O-Notation – Komplexitätsklassen
Bei der O-Notation erfolgt die Einordnung von Funktionen in Komplexitätsklassen. Eine Komplexitätsklasse beschreibt eine Menge von Funktionen.
Die formale Definition für die O-Notation lautet:
f(n) ∈ O(g(n)), wenn c∈Ν und m∈Ν existieren, sodass f(n) ≤ c ∗ g(n) für alle n≥m.
f(n) gehört also zur Komplexitätsklasse O(g(n)), wenn sich eine Konstante c finden lässt, sodass für alle Eingaben größer oder gleich m gilt: Das Ergebnis von f(n) ist kleiner als oder gleich dem Ergebnis c ∗ g(n).
In der Praxis ergeben sich daraus folgende gebräuchliche Komplexitätsklassen für die Notation. Sie sind sortiert nach der Effizienz der darin enthaltenen Funktionen.
Dabei enthält die jeweils nächsthöhere Komplexitätsklasse logischerweise alle Funktionen aus den vorherigen Klassen. Die lineare Komplexitätsklasse enthält also zum Beispiel alle Funktionen, die konstanten oder logarithmischen Aufwand besitzen.
O(1) – Konstanter Aufwand
Der sich ergebende Aufwand für die Laufzeit ist stets konstant, also unabhängig von der Eingabegröße des Algorithmus. Dieser terminiert immer gleich schnell.
Als Beispiel für den konstanten Aufwand kannst Du den Zugriff auf ein Element im Array nehmen, der unabhängig von der Anzahl der Elemente im Array ist.
O(log n) – Logarithmischer Aufwand
Bei einer Verdopplung der Eingabemenge wächst der Aufwand um einen beinahe konstanten Wert.
Ein Beispiel für den logarithmischen Aufwand ist die Suche nach dem kleinsten Element in einem Binärbaum, sofern die Elemente des Binärbaums sortiert sind.
O(n) – Linearer Aufwand
Der Aufwand des Algorithmus steigt linear mit der Eingabegröße an. Verdoppelt sich etwa die Menge des Inputs, so verdoppelt sich auch die Laufzeit.
Die lineare Suche nach einem Element in einer Liste hat einen linearen Aufwand. Im schlimmsten Fall steht das gesuchte Element an letzter Stelle und die gesamte Liste muss durchlaufen werden.
An diesem Beispiel sieht man gut, dass der tatsächliche Aufwand auch deutlich geringer ausfallen kann. Das gesuchte Element könnte auch an erster Stelle in der Liste stehen.
O(n ∗ log n) – Quasi-linearer Aufwand
Die Laufzeit des Algorithmus ist eine Kombination aus linearem und logarithmischen Aufwand und steigt etwas stärker als linear mit der Eingabegröße an.
O(n²) – Quadratischer Aufwand
Der Aufwand wächst quadratisch zur Eingabemenge. Verdoppelt sich die Eingabemenge, so vervierfacht sich die Laufzeit. Verzehnfacht sich die Eingabemenge, so verhundertfacht sich die Laufzeit bereits!
Bei großen Eingabemengen kann es hier also zu einer langen Laufzeit des Algorithmus kommen. Die Einordnung in Komplexitätsklassen kann helfen zu entscheiden, bei welchen Eingabemengen ein Algorithmus noch für die reale Anwendung geeignet ist.
Der Sortieralgorithmus Bubble Sort geht eine Menge an Elementen wiederholt durch, vergleicht jeweils zwei nebeneinander stehende Elemente und sortiert sie bei Bedarf um. Hier kann es beispielsweise im schlimmsten Fall zu einer quadratischen Laufzeit kommen.
Vergleich von Graphen der vorgestellten Komplexitätsklassen
Die Graphen der Funktionen, die man für die Notation verwendet, verdeutlichen noch einmal, wie schnell der Aufwand bei einem Algorithmus der jeweiligen Komplexitätsklasse wachsen kann.
Weitere Komplexitätsklassen
Algorithmen weniger effizienter Komplexitätsklassen werden in der Praxis normalerweise nicht verwendet. Ihr Aufwand steigt zu enorm und zu schnell mit der Eingabegröße an. Dazu gehören:
- O(n^k) mit k>2 – Polynomieller Aufwand
- O(2^n) – Exponentieller Aufwand
- O(n!) – Faktorieller Aufwand
Abb. 1: Graphen für die gängigen Komplexitätsklassen
O-Notation – Vergleich mit anderer Bachmann-Landau-Notation
Die O-Notation ist Teil der Bachmann-Landau-Notation. Streng genommen kennt diese aber auch andere Arten der Notation, um die Komplexität von Algorithmen zu beschreiben. Diese sollen hier der Vollständigkeit halber nicht unerwähnt bleiben.
| Notation | Erklärung |
| f(n) ∈ O(g(n)) | Bedeutet, dass g(n) eine obere Schranke für f(n) darstellt, also dass f(n) maximal so schnell wächst wie g(n). |
| f(n) ∈ o(g(n)) | Bedeutet, dass g(n) eine untere Schranke für f(n) darstellt, also dass f(n) mindestens so schnell wächst wie g(n). Wird in der Praxis eher selten verwendet, weil es meist darum geht, die Komplexität nach oben hin zu begrenzen. |
| f(n) ∈ θ(g(n)) | Bedeutet, dass g(n) gleichzeitig obere und untere Schranke für f(n) darstellt, also dass f(n) etwa genauso schnell wächst wie g(n). Wird in der Praxis ebenfalls kaum verwendet, sollte aber der Vollständigkeit halber erwähnt sein. |
O-Notation – Algorithmen und Datenstrukturen
Die folgende Tabelle ordnet einige bekannte Algorithmen und Datenstruktur-Operationen den Komplexitätsklassen der O-Notation zu.
O-Notation – Worst Case, Best Case und Average Case
Die Geschwindigkeit eines Algorithmus ist meist abhängig von seinem Input. In der Praxis ermittelt man daher oft Szenarien für Worst Case, Best Case und eventuell auch den Average Case. Das wird vor allem für Sortieralgorithmen oft gemacht.
Die Szenarien für die einfache lineare Suche in einer Liste können so aussehen.
- Best Case Szenario: Das gesuchte Element steht an erster Stelle. Es ist also egal, wie viele Elemente die Liste hat, der Algorithmus terminiert mit konstanter Laufzeit. Das Best Case Szenario liegt also in O(1).
- Worst Case Szenario: Das gesuchte Element steht an letzter Stelle, und es muss die gesamte Liste durchlaufen werden. Der Aufwand wächst linear mit der Anzahl an Elementen in der Liste, weshalb dieses Szenario in O(n) gehört.
- Average Case Szenario: In Wahrheit weiß man nicht, wie oft das gesuchte Element wo in der Liste stehen wird. Daher muss man eine Annahme treffen, um das Szenario zu betrachten, und kann zum Beispiel von einer Gleichverteilung ausgehen. In diesem Fall wäre das Average Case Szenario der Durchschnitt aus den Laufzeiten, die der Algorithmus für jede Eingabe benötigt.
O-Notation Rechenregeln
Die Bestimmung der Komplexitätsklasse für Funktionen richtet sich nach zwei Rechenregeln.
- Konstanten in der Formel werden eliminiert.
- Nur der am stärksten wachsende Summand ist relevant.
5n² + 17n + 37 ∈ O(n²)
Regel Nr. 2: Der erste Summand 5n² wächst in dieser Funktion am stärksten und ist daher als einziges relevant für die Einordnung in eine Komplexitätsklasse.
Regel Nr. 1: Die Konstante 5 im ersten Summand hat bei der Notation keinen Einfluss auf die Einordnung in die Komplexitätsklasse O(n²) und kann daher weggelassen werden.
Die Rechenregeln verdeutlichen, dass es bei der Notation vor allem um die Untersuchung großer Eingabemengen geht. Konstanten und schwächer wachsende Terme fallen bei hohen Eingabemengen immer weniger ins Gewicht und können daher bei der Notation weggelassen werden.
Somit kann es aber dazu kommen, dass der Schwellenwert m sehr groß wird, ab dem Funktionen der niedrigeren Komplexitätsklasse auch tatsächlich effizienter sind.
Vergleiche die beiden Funktionen 100n² und 0,01n³.
Erstere ist in der effizienteren Komplexitätsklasse O(n²) angesiedelt. Die Zweite befindet sich in der weniger effizienten Komplexitätsklasse O(n³).
Tatsächlich ist aber die letztere Funktion bis zu einer Eingabegröße von n=10.000 effizienter.
O-Notation – Beispiele und Lösungen
Einige Beispiele sollen die Verwendung der O-Notation in der Praxis verdeutlichen.
O-Notation Beispiel Bubble Sort
Der folgende Codeausschnitt stellt Pseudocode für den Sortieralgorithmus Bubble Sort dar.
function BubbleSort(array : array of items, length : array length)
for i = 0 to length - 1 do: // Äußere Schleife, in der das Array durchlaufen wird.
swapped = false;
for j = 0 to length - 1 do: // Innere Schleife, in der das Array noch einmal durchlaufen wird.
if (array[j+1] < array[j]) then
swap(array[j+1], array[j])
swapped = true
end if
end for
if (not swapped) then
break
end if
end for
end function return arrayFrage:
Wie lässt sich der Algorithmus in eine Komplexitätsklasse einordnen?
Antwort:
Die Eingabegröße n ist bei diesem Algorithmus die Länge des Arrays, das in die Methode hineingegeben wird. Weil das Array im schlimmsten Fall in beiden Schleifen komplett durchlaufen wird, ergibt sich daraus für die Laufzeit ein Aufwand von n ∗ n = n² ∈ O(n²).
O-Notation Rechenbeispiel
Das folgende Rechenbeispiel verdeutlicht die Zuordnung einer Funktion zu einer Komplexitätsklasse. Ähnlich sieht das Vorgehen auch für andere Funktionen aus.
Frage:
In welcher Komplexitätsklasse befindet sich die Formel f(n) = 2n² + n?
Antwort:
Den Rechenregeln der O-Notation nach ist f(n) = 2n² + n ∈ O(n²).
Begründung:
Nach Definition muss Folgendes gelten, damit die Antwort korrekt ist: 2n² + n ≤ c ∗ n²
Diese Gleichung kann man so umstellen:
2n² + n ≤ c ∗ n²
2 + 1/n ≤ c
Damit erfährt man, welchen Wert die Konstante c im Verhältnis zu n mindestens annehmen muss.
Nimmt man etwa einen Schwellenwert von m=1, so muss die Konstante c≥3 sein, denn:
2 + 1/n ≤ c
3 ≤ c
Nach dieser Bedingung kann man also für m=1 die Konstante c=3 wählen, bei der die ursprüngliche Behauptung 2n² + n ≤ c ∗ n² aufgeht. Damit erfüllt f(n) = 2n² + n die Bedingung, um in die Komplexitätsklasse O(n²) zu gehören.
O-Notation – Das Wichtigste
- Einfach erklärt schätzt die O-Notation in der Informatik den Aufwand von Algorithmen in Abhängigkeit ihrer Eingabegröße ein und macht sie damit vergleichbar.
- Die Komplexitätsklassen der O-Notation teilen Algorithmen ihrer Effizienz nach ein. Jede von ihnen stellt jeweils eine Menge von Funktionen dar.
- Die zwei O-Notation-Rechenregeln besagen, dass in der Funktion nur der am stärksten wachsende Summand betrachtet wird und in der Formel alle Konstanten eliminiert werden.
- Die O-Notation beschreibt bei Algorithmen und Datenstrukturen die obere Komplexitätsgrenze.
Nachweise
- Prof. Dr. Christian Böhm (2007). Komplexität von Algorithmen. dbs.ifi.lmu.de (19.10.2022)
- Prof. Dr. Margarita Esponda (2012). Die O-Notation. inf.fu-berlin.de (19.10.2022)
Schule 
Studium 
Ausbildung 
Karteikarten Erstelle und finde die besten Karteikarten.
Notizen Erstelle Notizen schneller als je zuvor.
Lernsets Alles was du brauchst an einem Ort.
Lernpläne Wöchentliche Ziele, Lern-Reminder, und mehr.
Spaced Repetition Nachhaltiger lernen.
AI powered learning Mithilfe unserer KI zum Lernerfolg
Blog 
