Was ist die O-Notation? 1. Teil
Angenommen, für eine Webseite soll ein Suchalgorithmus programmiert werden. Er soll so schnell wie möglich relevante Daten zum Suchbegriff liefern, und das unabhängig davon, wie alt die Textbeiträge sind und in welcher Form das Schlüsselwort in den Text eingebettet ist. Aber wie lässt sich sicherstellen, dass der Algorithmus jede Anfrage schnell genug beantwortet?
An dieser Stelle kommt die sogenannte O-Notation ins Spiel. Sie ermöglicht, die Leistung des Algorithmus einzuschätzen und so die richtige Wahl zu treffen.
In einem zweiteiligen Beitrag erklären wir, was genau es mit der O-Notation auf sich hat!:
Was ist die O-Notation?
Bei der O-Notation, auch asymptotische Notation und auf Englisch big O notation genannt, handelt es sich um eine Methode in der Informatik, mit der der Aufwand eines Algorithmus oder genauer die Komplexität von Funktionen im Abhängigkeit zu ihrer Eingabegröße eingeordnet werden kann. Dadurch macht die O-Notation vergleichbar, wie effizient Algorithmen sind.
Für jede Ausführung hat ein Algorithmus einen bestimmten Aufwand an Laufzeit. Diese benötigte Rechenzeit könnte zum Beispiel in Millisekunden angegeben werden.
Allerdings wäre die allgemeine Aussagekraft von so einer Messung gering. Denn je nach genutzter Hardware und Umfang der Eingabemenge für den Algorithmus ist die Laufzeit verschieden.
Die O-Notation soll nun aber gerade Algorithmen in ihren Laufzeiten vergleichbar machen.
Aus diesem Grund führt sie keine präzise Berechnung des Aufwands durch, sondern ordnet Algorithmen und Funktionen Komplexitätsklassen zu.
Inhalt
Die zentrale Frage bei der O-Notation
Die O-Notation betrachtet in erster Linie hohe Eingabegrößen. Die Frage dabei lautet: Wie sehr und wie schnell verändert sich die Laufzeit des Algorithmus, wenn die Eingabegröße zunimmt?
Angenommen, es gibt eine Liste mit x Elementen, und in dieser Liste soll ein bestimmtes Element gefunden werden. Dafür stehen zwei Suchalgorithmen zur Verfügung.
Hat die Liste 50 Elemente, wird sich die Laufzeit der beiden Algorithmen nicht großartig voneinander unterscheiden. Doch wenn in der Liste fünf Millionen oder sogar fünf Milliarden Elemente stehen, können die Laufzeiten der Algorithmen extrem weit auseinandergehen.
Die O-Notation beschreibt die obere Komplexitätsgrenze. Sie gibt also an, wie langsam der Algorithmus im schlimmsten Fall sein kann. Bei einer linearen Suche wird die Liste von vorne bis hinten Element für Element durchsucht.
Der schlimmste Fall wäre, wenn das gesuchte Element das letzte Element ganz am Ende der Liste ist, weil dann die komplette Liste durchlaufen werden muss. Andersherum kann der Aufwand aber auch sehr gering sein.
Nämlich dann, wenn das gesuchte Element gleich ganz am Anfang der Liste steht.
Überwiegend wird die O-Notation verwendet, um die Zeitkomplexität eines Algorithmus zu beschreiben. Möglich ist aber auch, die Platzkomplexität darzustellen.
In diesem Fall ist die Frage: Wie viel mehr Speicherplatz braucht ein Algorithmus, wenn die Eingabegröße zunimmt?
Welche Komplexitätsklassen gibt es bei der O-Notation?
Funktionen werden bei der O-Notation in Komplexitätsklassen eingeordnet. Dabei beschreibt eine Komplexitätsklasse eine Menge von Funktionen.
Formal ist die O-Notation wie folgt definiert:
| f(n) ∈ O(g(n)), wenn c ∈ N und m ∈ N existieren, wodurch für alle n ≥ m gilt, dass f(n) ≤ c * g(n). |
Demnach gehört f(n) zur Komplexitätsklasse O(g(n)), wenn eine Konstante c existiert. Dadurch gilt für alle Eingaben, die größer oder gleich m sind, dass das Ergebnis von f(n) kleiner oder gleich dem Ergebnis aus c * g(n) ist.
Was in der Theorie komplex klingt, führt in der Praxis zu gängigen Komplexitätsklassen für die Notation, die wir gleich auflisten.
Dabei haben wir die Klassen nach der Effizienz der Funktionen sortiert, die sie enthalten. Die nächsthöhere Klasse schließt logischerweise alle Funktionen der zuvor genannten Komplexitätsklassen ein.
- O(1) – konstanter Aufwand: Der Aufwand für die Laufzeit ist immer konstant, unabhängig davon, wie umfangreich die Eingabegröße des Algorithmus ist. Der Algorithmus beendet eine Aufgabe somit stets gleich schnell.
- O(log n) – logarithmischer Aufwand: Verdoppelt sich die Eingabemenge, erhöht sich der Aufwand um einen nahezu konstanten Wert.
- O(n) – linearer Aufwand: Der Aufwand des Algorithmus erhöht sich linear mit der Eingabegröße. Wenn sich die Menge der Eingaben zum Beispiel verdoppelt, verdoppelt sich auch die Laufzeit.
- O(n * log n) – quasi-linearer Aufwand: Die Laufzeit des Algorithmus kombiniert den linearen und den logarithmischen Aufwand miteinander. Dadurch steigt sie etwas stärker als linear mit der Eingabegröße an.
- O(n2) – quadratischer Aufwand: Der Aufwand erhöht sich im Quadrat zur Eingabemenge. Wenn sich die Eingabemenge zum Beispiel verdoppelt, vervierfacht sich also die Laufzeit.
Große Eingabemengen können dazu führen, dass die Laufzeit des Algorithmus sehr lang wird. Die Zuordnung zu den Komplexitätsklassen kann dabei helfen, die richtige Entscheidung zu treffen, welcher Algorithmus sich bei der vorhandenen Eingabemenge noch für die reale Anwendung eignet.
Die O-Notation verglichen mit anderen Formen der Bachmann-Landau-Notation
Die O-Notation zählt zur Bachmann-Landau-Notation. Diese kennt aber noch weitere Arten, um die Komplexität von Algorithmen dazustellen. Der Vollständigkeit halber wollen wir sie nicht unerwähnt lassen.
-
f(n) ∈ O(g(n)) bedeutet, dass g(n) die obere Begrenzung für f(n) bildet. Folglich wächst f(n) höchstens so schnell wie g(n).
-
f(n) ∈ o(g(n)) legt g(n) als untere Begrenzung für f(n) fest. Deshalb wächst f(n) mindestens genauso schnell wie g(n). Diese Notation wird aber eher selten verwendet, weil es in der Praxis üblicherweise darum geht, die Komplexität nach oben hin zu begrenzen.
-
f(n) ∈ θ(g(n)) heißt, dass g(n) sowohl die obere als auch die untere Begrenzung für f(n) ist. Demnach vergrößert sich f(n) annähernd im gleichen Tempo wie g(n). Auch diese Notation ist in der Praxis aber nur selten anzutreffen.
Mehr Ratgeber, Tipps und Anleitungen:
- 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
- Leitfaden: SEO und Social-Media – Wirtschaftliche und geschäftliche Leistungsvorteile
Thema: Was ist die O-Notation? 1. Teil
Übersicht:
Fachartikel
Verzeichnis
Über uns
- Die 5 größten Gefahren für externe Festplatten - 6. April 2024
- Eine E-Mail an mehrere Empfänger verschicken – so geht’s richtig - 15. März 2024
- Grundlegendes Wissen zu verteilten Datenstrukturen, 2. Teil - 7. März 2024