Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Zeitkomplexität und O-Notation
(siehe auch Wikipedia: Zeitkomplexität, Platzkomplexität, Landau-Symbol)


Zeitkomplexität

Für ein konkretes Problem bzw. einen konkreten Algorithmus ist die Laufzeit des Programms, also die Anzahl der Rechenschritte, unmittelbar von der Eingabe abhängig. Als Beispiel können Sortieralgorithmen betrachtet werden, die von der Vorsortierung der Daten profitieren. Sollen konkrete Angabe gemacht werden, müssten alle Eingabevarianten getestet werden. Dies ist aber nicht praktikabel.

Der Informatiker unterscheidet deshalb zwischen folgenden Fällen:

Beispiel: lineares Suchen einer Zahl in einem Feld mit der Länge n

Häufig wird der Begriff der Zeitkomplexität mit dem Worst-Case in Verbindung gebracht.

Die Zeitkomplexität T(n) eines Algorithmus gibt den größten Wert für die Anzahl der Elementaroperationen an, die der Algorithmus benötigt um ein Problem mit n Eingabedaten zu lösen.

Diese Definition der Zeitkomplexität genügt der landläufigen Vorstellung. Der Fachinformatiker führt den Begriff der Zeitkomplexität nicht auf die Anzahl von Elementaroperationen sondern auf Takte einer abstrakten Turingmaschine zurück.

Zeitkomplexitätsklassen

Der Informatiker versucht, die Probleme gemäß ihres Aufwandes in Klassen einzuteilen.

Polynomiale Algorithmen sind Algorithmen mit einem Zeitaufwand T, der wie folgt ausgedrückt werden kann:

T(n) = aknk + ak-1nk-1 + ... + a1n + a0, mit k ∈ N, ak, ..., a0 ∈ R, ak ≠ 0.

Sonderfälle:

  • konstanter Aufwand: k = 0
  • linearer Aufwand: k = 1
  • quadratischer Aufwand: k = 2
  • kubischer Aufwand: k = 3

Besonderheit:

  • anstelle des Polynoms kann auch eine Logarithmusfunktion mit beliebiger Basis treten: T(n) = logB(n) oder T(n) = n·logB(n)

Exponentielle Algorithmen sind Algorithmen mit einem Zeitaufwand, der wie folgt ausgedrückt werden kann:

T(n) = c·zn, mit z, c ∈ R, c ≠ 0, z > 1.

Besonderheit:

  • anstelle der Exponentialfunktion kann auch z. B. die Funktion T(n) = n! oder T(n) = nn treten.

Beispiele: Ein fiktiver Computer kann 106 Operationen pro Sekunde ausführen. Man berechne die Rechenzeit des Algorithmus für Eingaben der Länge n bei gegebener Zeitkomplexität T(n).

  Rechenzeit für n in Sekunden
T(n) n = 10 n = 100 n = 1000 n = 10000 n = 100000 n = 1000000
1

10-6 s

10-6 s 10-6 s 10-6 s 10-6 s 10-6 s
n 10-5 s 10-4 s 10-3 s 0,01 s 0,1 s 1 s
n2 10-4 s 0,01 s 1 s 100 s 10000 s 
≈ 2,8 d
1000000 s 
≈ 277 h 45 min
2n ≈ 0,001s ≈ 1,268·1024 s ≈ 4 · 1016 Jahre; 
zum Vergleich: Alter des Universums beträgt  ≈ 12 · 109 Jahre
log2(n) ≈ 3,2· 10-6 s ≈ 6,6·10-6 s ≈ 1,0·10-5 s ≈ 1,3·10-5 s ≈ 1,7·10-5 s ≈ 2,0·10-5 s
n·log2(n) ≈ 3,2· 10-5 s ≈ 6,6·10-4 s ≈ 1,0·10-2 s ≈ 0,13 s ≈ 1,7 s ≈ 20 s

Es scheint, dass exponentielle Algorithmen zur Lösung von Problemen nicht günstig sind, da bei einer Vergrößerung der Eingabemenge n die Rechenzeit enorm steigt.

Ein Algorithmus heißt effizient, wenn er ein vorgegebenes Problem mit möglichst geringem Ressourcenverbrauch (Zeit, Speicher) löst. Dies sind  Algorithmen von maximal polynomialer Ordnung.

O-Notation

In der Regel ist es schwierig oder gar unmöglich, die genaue Gleichung für den Zeitaufwand T(n) für einen Algorithmus anzugeben. Man versucht daher, den Aufwand asymptotisch abzuschätzen, d. h. man versucht eine möglichst einfache Funktion zu finden, die für große n die Funktion des Zeitaufwandes nach oben hin beschränkt. Es soll also gelten, dass T(n) ≤ c·f(n) gilt, ab einem bestimmten Element n0, wobei c eine positive Konstante ist. Diese Abschätzung wird auch asymptotische Ordnung O(f) bezeichnet. 

Hier nun die exakte, mathematische Formulierung der asymptotischen Ordnung: O(f) = {T | T: N R0+ und ∃c ∈ R+ ∃n0 N ∀n ≥ n0: T(n) ≤ c·f(n)}

Beispiel:

Gegeben sei die Funktion des Zeitaufwands T(n) = 3n2 – 6n + 9 Welche Funktion kann als Abschätzung benutzt werden?

Es handelt sich bei T(n) um eine quadratische Funktion, die wiederum mit einer quadratischen Funktion, nämlich f(n) = n2 asymptotisch angenährt werden soll. 
Damit muss also T(n) ≤ c·f(n), also 3n2 – 6n + 9 ≤ c·n2 gelten. Setzt man c = 3, so lässt sich die Gleichung elementar umformen und man erhält:

Für alle n ≥ 3 ist beschränkt der Ausdruck 3·n2 die Funktion T(n). Damit gilt für die Funktion T(n) ∈ O(n2). 

Demzufolge haben polynomiale Algorithmen vom Grad k stets einen Laufzeitaufwand von O(nk), exponentielle Algorithmen den Aufwand O(2n), O(n!) oder O(nn).

Zeitkomplexität von Ripplesort

Der Zeitaufwand bei Rippelsort (Worst-Case) wurde bereits berechnet. Es gilt: T(n) = 0,5·(n2 – n). Ripplesort hat demzufolge einen Zeitaufwand der Ordnung O(n2).

 



zur Startseite
© Tino Hempel 1997 - 2007 Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.