Laufzeitkomplexität

Die Laufzeitkomplexität bezeichnet das Laufzeitverhalten eines Algorithmus in Abhängigkeit vom Umfang seiner Eingabedaten. Man verwendet dazu häufig die sogenannte 𝒪-Notation, die auf den amerikanischen Informatiker Donald E. Knuth zurückgeht und auf einem noch älteren Landau-Symbol basiert. Der Buchstabe 𝒪 steht dabei für (liegt in der Größen-)Ordnung von, Knuth hat allerdings die Bedeutung des Symbols abgewandelt.

Die 𝒪-Notation gibt keinen exakten Wert an, sondern stellt eine Abschätzung dar, basierend auf der Konstruktion des verwendeten Algorithmus. Man schreibt 𝒪(f), wobei f eine Funktion im reellen Zahlenraum ist, die den Zusammenhang zwischen Volumen der verarbeiteten Daten und der Laufzeit des Algorithmus aufzeigt. Es werden allerdings nur stark vereinfachte Funktionen verwendet, typischerweise einfache Potenz-, Wurzel- oder Logarithmusfunktionen. Es wird auch keine exakte mathematische Notation verwendet, sondern einfach der Term aus der Funktionsgleichung hingeschrieben, der aus x den Wert f(x) berechnet. Dieser Term wird soweit vereinfacht, dass keine Summen und keine konstanten Faktoren mehr übrig sind.

Typische Laufzeitkomplexitätsangaben sind:

𝒪(1)

konstante Komplexität, die Laufzeit hängt nicht von der Datenmenge ab.

z.B. Arrayzugriff, Hashtable

𝒪(n)

lineare Komplexität, die Laufzeit ist propertional zur Datenmenge.

z.B. Schleife über ein Array um einen Wert zu finden, Einlesen einer Treffermenge aus der Datenbank

𝒪(n²)

quadratische Komplexität, eine doppelte Datenmenge vervierfacht die Laufzeit

z.B. Bubble-Sort

𝒪(log n)

logarithmische Komplexität, wird die Datenmenge jeweils verdoppelt, steigt die Laufzeit linear an

z.B. Suchbäume

𝒪(n log n)

superlineare Komplexität, liegt zwischen 𝒪(n) und 𝒪(n²). Tritt zum Beispiel auf, wenn eine Schleife über eine Baumsuche gebildet wird.

z.B. optimierte Sortieralgorithmen wie Quicksort

𝒪(2ⁿ)

exponentielle Komplexität, die Laufzeit verdoppelt sich, wenn die Datenmenge um eine Einheit größer wird.

z.B. Bilden aller Paare einer Menge, Türme von Hanoi als rekursiver Algorithmus

𝒪(n!)

faktorielle Komplexität, die Laufzeit wächst mit der Fakultät der Datenmenge.

z.B. Problem des Handlungsreisenden

Für die Abschätzung der Komplexität wird immer der Teil des Algorithmus betrachtet, der die höchste 𝒪-Klasse hat. Wenn beispielsweise ein Bubble-Sort auf eine lineare Suche folgt, würde man nicht 𝒪(n + n²) schreiben, sondern nur 𝒪(n²). Der lineare Teil fällt bei steigenden n nicht mehr ins Gewicht. Ebenso würde man nicht 𝒪(3n²) schreiben, um einen besonders langsamen 𝒪(n²) Algorithmus zu bezeichnen. Für die Abschätzung des Laufzeitverhaltens ist das nicht wichtig.

Etwas anderes wäre eine Schleife, die über eine Datenmenge läuft und sie pro Durchlauf per Bubblesort sortiert. Hier läge eine Komplexität 𝒪(n³) vor. Man kann aber nicht generell sagen, dass drei ineinander geschachtelte Schleifen eine 𝒪(n³) Komplexität bedeuten. Wird pro Durchlauf nur eine Teilmenge der Daten betrachtet, kann die Komplexität auch geringer sein.

Weiterführende Hinweise im WWW findet man mittels Begriffen wie Algorithmenanalyse oder Landau-Symbole.