Was ist die O-Notation? 1. Teil

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?

Anzeige

Was ist die O-Notation 1. Teil

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.

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).
Besucher lesen auch gerade folgenden Beitrag:  Fake News erkennen - und dagegen vorgehen

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:

Anzeige

Thema: Was ist die O-Notation? 1. Teil 

-

Übersicht:
Fachartikel
Verzeichnis
Über uns


it datenbanken99

Autoren Profil:
FB/Twitter

Veröffentlicht von

Autoren Profil:

Gerd Tauber - Programmierer, Samuel Wilders IT- Experte und Markus Berthold Inhaber einer Medienagentur, Ferya Gülcan Inhaberin Onlinemedien-Agentur, Christian Gülcan Inhaber Artdefects Media Verlag, schreiben hier Wissenswertes zum Thema IT, Internet, Hardware, Programmierung, Social-Media, Software und IT-Jobs.

Kommentar verfassen