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:

• Worst-Case:
  ungünstigster Fall – Maximum aller möglichen Laufzeiten bei einer Eingabe fester Länge n
• Average-Case:
  mittlerer Fall, Durchschnitt – arithmetisches Mittel aller möglichen Laufzeiten bei einer Eingabe fester Länge n
• Best-Case:
  günstigster Fall – Minimum aller möglichen Laufzeiten bei einer Eingabe fester Länge n

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

• Worst-Case:
  ungünstigster Fall – Element steht am Ende des Feldes – gesamtes Feld muss durchlaufen werden (n Schritte) – Worst-Case: n
• Average-Case:
  mittlerer Fall, Durchschnitt – arithmetisches Mittel pendelt sich gemäß Statistik bei n/2 ein
• Best-Case:
  günstigster Fall – Element steht am Anfang des Feldes – nur ein Schritt erforderlich – Best-Case: 1

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 10⁶ 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 n₀, 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 → R₀⁺ und ∃c ∈ R⁺ ∃n₀ ∈ N ∀n ≥ n₀: T(n) ≤ c·f(n)}

Beispiel:

Gegeben sei die Funktion des Zeitaufwands T(n) = 3n² – 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) = n² asymptotisch angenährt werden soll. 
Damit muss also T(n) ≤ c·f(n), also 3n² – 6n + 9 ≤ c·n² gelten. Setzt man c = 3, so lässt sich die Gleichung elementar umformen und man erhält:

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

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

Zeitkomplexität von Ripplesort

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

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.