AlgorithmenAsymptotische Komplexität | 
|
Komplexität von Algorithmen
Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die Laufzeit des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf ein bestimmtes zugrunde gelegtes Maschinenmodell. Die Maschine muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen.
Die Laufzeit hängt dann im Allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird.
Beispiel: Die Laufzeit eines Sortieralgorithmus ist umso größer, je mehr Elemente zu sortieren sind.
Bei einer vorsortierten Eingabefolge benötigt der Algorithmus möglicherweise weniger Schritte als bei einer unsortierten Eingabefolge gleicher Länge.
Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität. Die Zeitkomplexität ist eine Funktion T(n) in Abhängigkeit von der Problemgröße n. Der Wert von T(n) ist die Laufzeit des Algorithmus im schlechtesten Fall (worst case), d.h. die Anzahl der Schritte, die bei einer beliebigen Eingabe höchstens ausgeführt werden.
Gelegentlich betrachtet man auch für das Verhalten von T(n) im Durchschnitt (average case), d.h. die Anzahl der Schritte, die bei einer großen Zahl von zufällig gewählten Eingaben der Länge n im Mittel erforderlich sind.
Die genaue Anzahl der Schritte, die ein Algorithmus ausführt, hängt natürlich von der konkreten Implementation des Algorithmus ab. Tatsächlich kommen in der Implementation eines Sortieralgorithmus nicht nur Vergleiche und Vertauschungen vor, sondern noch weitere Schritte wie etwa das Erhöhen von Schleifenzählern u. ä.
Um Algorithmen unabhängig von den Details der Implementation bewerten zu können, wird die Zeitkomplexität mithilfe der O-Notation angegeben. Die O-Notation gibt nur die Größenordnung der Komplexität wieder, d.h. ob es sich z.B. um eine linear, quadratisch oder exponentiell wachsende Funktion handelt. Die Größenordnung wird in Form einer Komplexitätsklasse angegeben.
Definition: Sei f : 
eine Funktion. Die Menge O(f) enthält alle Funktionen g, die ab einem gewissen n0 höchstens so schnell wachsen wie f, abgesehen von jeweils einem konstanten Faktor c:
O(f) = { g : | 
c>0 n0 
n
n0 : g(n) 
c·f(n) }.
In Worten: O(f) enthält alle Funktionen g, für die es eine Konstante c und eine Zahl n0 gibt, sodass für alle nn0 gilt: g(n) ist kleiner oder gleich c·f(n).
Es ist auch üblich, die Funktionen mit Argument n zu schreiben, also g(n) O(f(n)).
Beispiel: Ist g(n) = 2n2 + 7n – 10 und f(n) = n2, so gilt:
g(n) O(f(n)),
denn mit c = 3 und ab n0 = 5 gilt:
2n2 + 7n – 10 c·n2.
Man sagt: Die Funktion g(n) liegt in O(n2).
Zur Veranschaulichung zeigt Bild 1 eine Funktion g(n), die ab n0 unterhalb der Geraden f(n) = 1/2 n liegt. Somit gilt g(n) O(n).
| |
| Bild 1: Funktion g(n) in O(n) | |
Um eine Komplexitätsklasse zu bezeichnen, gibt man immer die einfachste Funktion an, die geeignet ist, die jeweilige Komplexitätsklasse zu repräsentieren. Tatsächlich handelt es sich bei O(2n2 + 7n – 10) und O(n2) um dieselben Mengen, man wählt aber O(n2) als Bezeichnung.
Die Menge O(n2) ist die Komplexitätsklasse aller höchstens quadratisch wachsenden Funktionen. Entsprechend ist O(n) die Menge der höchstens linear wachsenden Funktionen, O(log(n)) die Menge der höchstens logarithmisch wachsenden Funktionen, O(1) sind die durch eine Konstante beschränkten Funktionen, O(nk) die höchstens polynomiell wachsenden Funktionen, O(2n) die höchstens exponentiell zur Basis 2 wachsenden Funktionen.
Beispiel: 10n + 5 log(n) + 8 O(n)
8n O(n2)
65 O(1)
n1000 O(2n)
log10(n) O(log(n))
Bei der Klasse der logarithmisch wachsenden Funktionen kommt es nicht auf die Basis des Logarithmus an, denn es ist
loga(n) = c·logb(n) mit c = loga(b).
Die O-Notation abstrahiert aber von konstanten Faktoren.
Wenn wir die Komplexität eines Algorithmus angeben, schreiben wir oft etwa: Der Algorithmus hat eine Komplexität von O(n2). Die Komplexität ist aber eine Funktion, während O(n2) eine Menge von Funktionen ist. Gemeint ist daher: Die Komplexität des Algorithmus liegt in O(n2) oder: Der Algorithmus hat eine Komplexität von T(n) mit T(n) O(n2).
Da O(n2) eine Menge ist, verwenden wir die korrekte Schreibweise T(n) O(n2) und nicht T(n) = O(n2) wie gelegentlich zu lesen ist.
O, Ω und Θ
Wird die Zeitkomplexität eines Algorithmus beispielsweise mit T(n) O(n2) angegeben, so bedeutet dies, dass der Algorithmus höchstens quadratisch viele Schritte benötigt. Streng genommen besagt diese Angabe nicht, dass der Algorithmus tatsächlich quadratisch viele Schritte benötigt.
Es könnte sich etwa auch um einen linearen Algorithmus handeln. Ein linearer Algorithmus benötigt auch höchstens quadratisch viele Schritte. Beträgt die Komplexität des Algorithmus beispielsweise T(n) = 10 n, so gilt ab n0 = 10, dass T(n) n2 ist. Also ist T(n) O(n2).
Eine Komplexitätsklasse O(f(n)) kann nur zur Abschätzung von T(n) nach oben, als obere Schranke dienen. Es wäre wenig sinnvoll, etwa zu sagen: "Der Algorithmus benötigt mindestens O(n) Schritte". Denn dies würde nach Definition der Komplexitätsklasse O(n) bedeuten, dass der Algorithmus mindestens höchstens c·n Schritte benötigt.
Zu einer genaueren Charakterisierung von T(n) sind noch andere Komplexitätsklassen erforderlich.
Definition: Sei f : eine Funktion. Die Menge Ω(f) enthält alle Funktionen g, die ab einem gewissen n0 mindestens so schnell wachsen wie f, abgesehen von jeweils einem konstanten Faktor c:
Ω(f) = { g : | c>0 n0 nn0 : g(n) c·f(n) }.
In Worten: Ω(f) enthält alle Funktionen g, für die es eine Konstante c und eine Zahl n0 gibt, sodass für alle nn0 gilt: g(n) ist größer oder gleich c·f(n).
Beispiel: Ist g(n) = 2n2 + 7n – 10 und f(n) = n2, so gilt:
g Ω(f),
denn mit c = 1 und ab n0 = 2 gilt:
2n2 + 7n – 10 c·n2.
Die betrachtete Beispielfunktion g(n) liegt also sowohl in O(n2) als auch in Ω(n2), d.h. sie wächst sowohl höchstens als auch mindestens quadratisch, also genau quadratisch.
Um die Größenordnung einer Funktion genau anzugeben, wird die Klasse Θ(f) verwendet; der Buchstabe Θ ist das griechische Theta.
Definition: Θ(f) = O(f) 
Ω(f)
Beispiel: Eine grobe Analyse ergibt, dass Insertionsort im schlechtesten Fall höchstens n2 Schritte ausführt, denn das Verfahren muss jede der n Zahlen in ein schon sortiertes Teilstück einsortieren, wobei das Teilstück natürlich aus höchstens n Zahlen besteht. Daher gilt für die Zeitkomplexität T(n) von Insertionsort im schlechtesten Fall
T(n) O(n2).
Eine genauere Analyse zeigt, dass es einen Fall gibt, in dem Insertionsort mindestens (n-1)·n/2 Schritte benötigt. Daher gilt für die Zeitkomplexität T(n) von Insertionsort im schlechtesten Fall auch
T(n) Ω(n2).
Damit lässt sich die Zeitkomplexität T(n) von Insertionsort im schlechtesten Fall also charakterisieren durch
T(n) Θ(n2).
Komplexität von Problemen
Hat man einen konkreten Algorithmus zur Lösung eines Problems vorliegen, so kann man abschätzen, wie viele Schritte der Algorithmus höchstens benötigt. Die Komplexität des Algorithmus stellt eine obere Schranke für die Komplexität des Problems dar.
Es stellt sich dann die Frage, ob es möglicherweise einen schnelleren Algorithmus zur Lösung des Problems gibt oder überhaupt geben kann.
Häufig lässt sich eine untere Schranke für das Problem angeben, d.h. man kann sagen, wie viele Schritte jeder Algorithmus mindestens ausführen muss, um das Problem zu lösen. Wie bei den oberen Schranken wird ein bestimmtes Algorithmen- oder Maschinenmodell zugrunde gelegt, damit der Begriff Schritt klar ist.
Um beispielsweise n Zahlen zu sortieren, muss jeder Algorithmus sich die Zahlen ja zumindest einmal anschauen. Ein sequentieller Algorithmus, der sich in einem Schritt eine Zahl anschauen kann, benötigt also mindestens T(n) = n Schritte, um die Zahlen zu sortieren. Also ist T(n) = n eine untere Schranke für das Sortierproblem, bezogen auf das erwähnte sequentielle Algorithmenmodell.
Auch hier kommt es nicht auf konstante Faktoren c an, es soll im Wesentlichen egal sein, ob ein Algorithmus etwa in einem Schritt eine, zwei oder 10 Zahlen verarbeiten kann. Und für allzu kleine Problemgrößen unterhalb von n0 mögen möglicherweise Sonderbedingungen gelten, sodass es auch hier nur auf das asymptotische Verhalten für nn0 ankommt.
Interessant ist also wiederum nur die Größenordnung der unteren Schranke, d.h. ob es sich z.B. um eine lineare, quadratische oder exponentielle Funktion handelt. Die Größenordnung wird wieder durch eine Funktionenklasse ausgedrückt.
Wie wir eben gesehen haben, liegt eine untere Schranke für das Sortierproblem in Ω(n). Eine obere Schranke liegt in O(n2), z.B. mit dem Sortierverfahren Insertionsort. Es stellt sich die Frage, ob sich die Diskrepanz zwischen diesen beiden Funktionen n und n2 beseitigen lässt, d.h. ob sich eine schärfere untere oder eine schärfere obere Schranke finden lässt.
Tatsächlich ist beides der Fall: Die untere Schranke lässt sich, zumindest für Verfahren, die auf Vergleichen beruhen, auf Ω(n log(n)) verbessern (Untere Schranke für das Sortieren), und die obere Schranke lässt sich ebenfalls auf O(n log(n)) verbessern, z.B. mit dem Sortierverfahren Heapsort.
Definition: Gegeben sei ein Problem und ein Algorithmus mit der Zeitkomplexität T(n) zur Lösung des Problems.
Der Algorithmus ist asymptotisch optimal, wenn Ω(T(n)) eine untere Schranke für das Problem ist.
Das Sortierverfahren Heapsort ist daher optimal, da es die untere Schranke für das Sortierproblem erreicht.
Siehe auch: [Obere und untere Schranken] oder
 |
 H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum Datenschutz © Created: 05.03.1997 Updated: 04.06.2018 |
 |
