Komplexität von Algorithmen - die O-Notation

Die O-Notation (engl. Big-Oh-Notation) stellt ein Hilfsmittel zur Untersuchung der Laufzeit eines Algorithmus dar.

Historisches

Eingeführt wurde die Symbolik der O-Notation durch den englischen Mathematiker Paul Bachmann (1837-1920) im Jahr 1894 in seinem Werk "Analytische Zahlentheorie". Später machte der Zahlentheoretiker Paul Landau (1877-1938) davon Gebrauch, weshalb die O-Notation gern auch als Schreibweise Landau'scher Symbole bezeichnet wird.

Zielsetzung

Das Ziel ist die Untersuchung der Laufzeitkomplexität von Algorithmen. Hierbei verfolgt man im Allgemeinen drei Grundgedanken:

1. Die Laufzeit eines Algorithmus soll in Abhängigkeit von der Anzahl an Eingabedaten n des Algorithmus untersucht werden. Es soll eine Funktion f in Abhängigkeit von der Anzahl der Eingabewerte n gefunden werden, welche die Laufzeit des Algorithmus wiedergibt: f(n).
2. Die angegebene Funktion f(n) soll unabhängig von rechnerspezifischen Details (tatsächlicher zeitlicher Aufwand) sein, daher ist von konstanten Faktoren c zu abstrahieren. Mit Laufzeit ist hier also nicht die zeitliche Dauer gemeint, die ein Algorithmus bis zu seiner Terminierung benötigt, sondern die Anzahl an Basis-Operationen, die der Algorithmus in Abhängigkeit von der Anzahl an Eingabedaten ausführen muss.
3. Die Funktion, die mittels O-Notation zur Kennzeichnung der Laufzeit angegeben wird, stellt - multipliziert mit einem rechnerabhängigen Faktor - eine obere Schranke für die tatsächliche Laufzeitfunktion dar, wenn die Anzahl der Eingabewerte einmal einen bestimmten Wert überschritten haben. Also untersucht man mit der O-Notation immer die Laufzeit im ungünstigsten Fall, im "worst case". Meist sucht man nicht irgendeine Funktion, welche (wiederum multipliziert mit der rechnerabhängigen Konstante) die tatsächliche Laufzeit majorisiert, sondern die kleinste. So würde eine Funktion g(n), zu welcher n² eine obere Schranke bildet, ebenfalls von n³ majorisiert werden, dies ist jedoch unerheblich, da n² eine "kleinere" Majorante zu g(n) darstellt, als n³. Allgemein sucht man eine Funktion f(n), für welche gilt: "c * f(n) ≥ g(n)", wobei g(n) die eigentliche Laufzeit und c die systemabhängige Konstante bezeichnet. Ist c * f(n) die kleinste Majorante von g(n), so kann dieser Term auch "Asymptote" von g(n) genannt werden, womit die Angabe der Laufzeit mittels O-Notation oft auch als "asymptotische Laufzeitkomplexität" bezeichnet wird.

Definition

Eine mögliche mathematische Definition und zugleich auch die gebräuchlichste ist folgende:

Gesprochen würde dies heissen: "O(f(n)) ist die Menge aller Funktionen g(n), für die es zwei Konstanten n₀ und c gibt, so dass für alle n ≥ n₀ gilt: g(n) ≤ c * f(n)".

Komlexitätsklassen

Eine kurze Zusammenfassung der wichtigsten Laufzeitkomplexitäten und in welchen praktischen Anwendungen man sie wiederfinden kann:

• logarithmische Komplexität: O(log(n)); kommt z.B. bei der "binären Suche" vor sowie bei allen "square-and-multiply"-Verfahren; diese Komplexität ist sehr günstig, da die Laufzeit noch nicht einmal linear wächst, beispielsweise kommt es durch Quadrieren von n gerade einmal zu einer Verdopplung der Laufzeit
• lineare Komplexität: O(n); z.B. bei der Suche in einem unsortierten Feld; diese Komplexität sollte das primäre Ziel eines Algorithmenentwurfs sein, ist aber nur selten erreichbar
• n*log(n)-Komplexität: O(n*log(n)); die Laufzeit einiger der schnellsten Sortieralgorithmen wird dadurch charakterisiert (z.B. Mergesort); ist noch sehr günstig, wenn auch nicht mehr linear
• quadratische Komplexität: O(n²); in der Praxis charakterisierend für den Bubblesort-Algorithmus oder z.B. die Multiplikation einer Matrix mit einem Vektor; ist nicht mehr so günstig, da eine Verdopplung der Eingabedaten eine Vervierfachung der Laufzeit nach sich zieht, jedoch immernoch vertretbar
• kubische Komplexität: O(n³); z.B. bei der Multiplikation zweier Matrizen; ist noch ungünstiger
• exponentielle Komplexität: O(cⁿ); katastrophal schon für kleine n
• gemäß Fakultätsfunktion wachsende Komplexität: O(n!); katastrophal schon für kleine n
• superexponentielle Komplexität: O(nⁿ); katastrophal schon für kleine n
  

Quelle: linux-related.de

Komplexität von vergleichsbasierten Sortierverfahren

Quelle: de.wikipedia.org

» drucken: pdf | html