Was ist die O-Notation? 2. Teil
Die Informatik nutzt die O-Notation, um die Komplexität von Algorithmen in Abhängigkeit zu ihrer Eingabegröße einzuordnen. Etabliert von den deutschen Zahlentheoretikern Bachmann und Landau, beschreibt das O in der O-Notation die obere Grenze, die die Funktionen innerhalb einer Komplexitätsklasse nicht überschreiten.
In einem zweiteiligen Beitrag erklären wir die O-Notation genauer. Dabei haben wir im 1. Teil beantwortet, was genau die O-Notation ist, um welchen zentralen Aspekt es dabei geht und welche Komplexitätsklassen die O-Notation kennt.
Hier ist der 2. Teil!:
Inhalt
Was bedeuten Worst, Best und Average Case?
Wie schnell ein Algorithmus ist, hängt meist von seinem Input ab. In der Praxis werden deshalb oft die Szenarien für den Worst Case, den Best Case und eventuell auch für den Average Case ermittelt. Vor allem bei Sortieralgorithmen ist diese Vorgehensweise üblich.
Bei einer einfachen, linearen Suche in einer Liste könnten die drei Szenarien zum Beispiel so aussehen:
- Best Case: Das gesuchte Element steht gleich an der ersten Stelle. Wie viele Elemente die Liste hat, spielt deshalb keine Rolle. Denn die Laufzeit des Algorithmus bleibt immer gleich. Der Best Case liegt demnach in O(1).
- Worst Case: Das gesuchte Element steht ganz hinten in der Liste. Folglich muss sie komplett durchlaufen werden. Weil der Aufwand linear mit der Anzahl an Elementen in der Liste steigt, gehört der Worst Case in O(n).
- Average Case: In der Realität ist nicht bekannt, wo und wie oft das gesuchte Element in der Liste auftaucht. Um das Szenario zu betrachten, muss aus diesem Grund eine Annahme getroffen werden. Dabei ist zum Beispiel möglich, eine Gleichverteilung zu vermuten. In diesem Fall ergibt sich das Average Case Szenario aus dem Durchschnitt der Laufzeiten, die der Algorithmus pro Eingabe braucht.
Wie lauten die Rechenregeln bei der O-Notation?
Um die Komplexitätsklasse für Funktionen zu bestimmen, finden zwei Rechenregeln Anwendung:
-
Konstanten in der Formel werden beseitigt.
-
Relevant ist nur der Summand, der am stärksten wächst.
Ein Beispiel
3n² + 15n + 25 ∈ O(n²)
In dieser Funktion wächst der erste Summand 3n² am stärksten. Für die Einordnung in eine Komplexitätsklasse ist deshalb auch nur er relevant. (Regel 2)
Auf die Einordnung in die Komplexitätsklasse O(n) hat die Konstante 3 im ersten Summand bei der Notation keinen Einfluss. Deshalb kann sie entfallen. (Regel 1)
Die Rechenregeln zeigen auf, dass es bei der Notation vor allem darum geht, große Eingabemengen zu untersuchen. Konstanten und Werte, die schwächer wachsen, machen sich bei hohen Eingabemengen zunehmend weniger bemerkbar.
Deshalb können sie bei der Notation entfallen. Allerdings kann dies dazu führen, dass der Schwellenwert m, ab dem Funktionen der niedrigeren Komplexitätsklasse tatsächlich effizienter sind, sehr groß wird.
Beispiel
Es gibt zwei Funktionen, nämlich 100n² und 0,0n³. Die erste Funktion gehört in die effizientere Komplexitätsklasse O(n²), während sich die zweite Funktion in der weniger effizienten Komplexitätsklasse O(n³) befindet.
Bis zu einer Eingabegröße von n = 10.000 ist die zweite Funktion aber tatsächlich effizienter.
Ein Rechenbeispiel für die Zuordnung zu einer Komplexitätsklasse bei der O-Notation
Anhand eines Beispiels lässt sich am besten nachvollziehen, wie bei der O-Notation eine Funktion einer Komplexitätsklasse zugeordnet wird. Bei anderen Funktionen gestaltet sich die Vorgehensweise ähnlich.
Frage: Zu welcher Komplexitätsklasse gehört die Formel f(n) = 2n² + n?
Lösung: Nach den Rechenregeln der O-Notation entspricht f(n) = 2n² + n ∈ O(n²).
Erklärung: Für eine korrekte Antwort muss per Definition gelten, dass 2n² + n ≤ c * n². Diese Gleichung lässt sich wie folgt umstellen:
2n² + n ≤ c * n²
2 + 1/n ≤ c
Damit steht fest, welchen Wert die Konstante c im Verhältnis zu n mindestens haben muss. Wird nun zum Beispiel ein Schwellenwert m = 1 angenommen, muss die Konstante c ≥ 3 sein:
2 + 1/n ≤ c
3 ≤ c
Nach dieser Bedingung ist es möglich, die Konstante c = 3 für m = 1 zu wählen. Denn die ursprüngliche Behauptung 2n² + n ≤ c * n² geht damit auf. Gleichzeitig erfüllt f(n) = 2n² + n die Bedingung, um in die Komplexitätsklasse O(n²) eingeordnet zu werden.
Das Wichtigste zur O-Notation noch einmal auf einen Blick
-
Bei Algorithmen und Datenstrukturen beschreibt die O-Notation die obere Komplexitätsgrenze.
-
In der Informatik schätzt die O-Notation den Aufwand von Algorithmen in Abhängigkeit zu ihrer Eingabegröße ein. Dadurch werden Algorithmen vergleichbar.
-
Die Komplexitätsklassen der O-Notation ordnen Algorithmen nach ihrer Effizienz. Jede davon stellt jeweils eine Menge an Funktionen dar.
-
Die beiden Rechenregeln der O-Notation besagen, dass nur der Summand mit dem stärksten Wachstum betrachtet wird und in der Formal alle Konstanten weggelassen werden können.
-
Voraussetzung für die O-Notation ist, dass es eine Konstante c gibt, die von n unabhängig ist, damit für alle Elemente f(n) ≤ c * g(n) gilt. Existiert diese Konstante nicht, gehört f(n) nicht zur Komplexitätsklasse O(g(n)).
Mehr Ratgeber, Tipps und Anleitungen:
- Was ist die O-Notation? 1. Teil
- Infos zu Listen als Datenstruktur
- Die wichtigsten Infos rund um Suchalgorithmen, 2. Teil
- Die wichtigsten Infos rund um Suchalgorithmen, 1. Teil
- KI-basierte Code-Sicherheit: Wie KI-Systeme unser digitales Leben sicherer machen
- 3 wichtige Aufgaben von KI-Systemen im Recruiting
- Starlink als Mittel zur Förderung von Bildung und Wissenschaft
- 7 Tipps für einen DSGVO-gerechten Umgang mit Daten im Homeoffice
Thema: Was ist die O-Notation? 2. Teil
Übersicht:
Fachartikel
Verzeichnis
Über uns
