Algorithmen

Asymptotische Komplexität

 English version  aufwärts

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 Maschinen­modell. 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 Sortier­algorithmus ist umso größer, je mehr Elemente zu sortieren sind.

Bei einer vor­sortierten Eingabefolge benötigt der Algorithmus möglicher­weise 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 Zeit­komplexität. Die Zeit­komplexitä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 Sortier­algorithmus nicht nur Vergleiche und Ver­tauschungen vor, sondern noch weitere Schritte wie etwa das Erhöhen von Schleifen­zählern u. ä.

Um Algorithmen unabhängig von den Details der Implementation bewerten zu können, wird die Zeit­komplexität mithilfe der O-Notation angegeben. Die O-Notation gibt nur die Größen­ordnung der Komplexität wieder, d.h. ob es sich z.B. um eine linear, quadratisch oder exponentiell wachsende Funktion handelt. Die Größen­ordnung wird in Form einer Komplexitätsklasse angegeben.

Definition:  Sei f : natürliche Zahlen Pfeil nach rechts reelle Zahlen 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 : natürliche Zahlen Pfeil nach rechts reelle Zahlen  |   es existiert c>0   es existiert n0 Element natürliche Zahlen   für alle ngrößer gleichn0  :  g(nkleiner gleich c·f(n) }.

In Worten: O(f) enthält alle Funktionen g, für die es eine Konstante c und eine Zahl n0 gibt, so dass für alle ngrößer gleichn0 gilt:  g(n) ist kleiner oder gleich  c·f(n).

Es ist auch üblich, die Funktionen mit Argument n zu schreiben, also  g(nElement O(f(n)).

Beispiel:  Ist  g(n) = 2n2 + 7n – 10   und   f(n) = n2, so gilt:

g(nElement O(f(n)),

denn mit c = 3 und ab n0 = 5 gilt:

2n2 + 7n – 10 kleiner gleich c·n2.

Man sagt: Die Funktion g(n) liegt in O(n2).

Zur Ver­anschaulichung zeigt Bild 1 eine Funktion g(n), die ab n0 unterhalb der Geraden f(n) = 1/2 n liegt. Somit gilt g(nElement O(n).

Bild 1: Funktion g(n) in 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  Element O(n)

8n  Element  O(n2)

65  Element  O(1)

n1000  Element  O(2n)

log10(n)  Element  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(nElement O(n2).

Da O(n2) eine Menge ist, verwenden wir die korrekte Schreibweise T(nElement O(n2) und nicht T(n) = O(n2) wie gelegentlich zu lesen ist.

O, Ω und Θ

Wird die Zeit­komplexität eines Algorithmus beispielsweise mit T(nElement 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) kleiner gleich n2 ist. Also ist T(nElement 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 : natürliche Zahlen Pfeil nach rechts reelle Zahlen 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 : natürliche Zahlen Pfeil nach rechts reelle Zahlen  |   es existiert c>0   es existiert n0 Element natürliche Zahlen   für alle ngrößer gleichn0  :  g(ngrößer gleich c·f(n) }.

In Worten: Ω(f) enthält alle Funktionen g, für die es eine Konstante c und eine Zahl n0 gibt, so dass für alle ngrößer gleichn0 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 Element Ω(f),

denn mit c = 1 und ab n0 = 2 gilt:

2n2 + 7n – 10  größer gleich c·n2.

Die betrachtete Beispiel­funktion 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ößen­ordnung einer Funktion genau anzugeben, wird die Klasse Θ(f) verwendet; der Buchstabe Θ ist das griechische Theta.

Definition:        Θ(f)  =  O(f)  Durchschnitt  Ω(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 Zeit­komplexität T(n) von Insertionsort im schlechtesten Fall

T(nElement 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 Zeit­komplexität T(n) von Insertionsort im schlechtesten Fall auch

T(nElement Ω(n2).

Damit lässt sich die Zeit­komplexität T(n) von Insertionsort im schlechtesten Fall also charakterisieren durch

T(nElement Θ(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öglicher­weise 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 Maschinen­modell 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 Sortier­problem, bezogen auf das erwähnte sequentielle Algorithmen­modell.

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 Problem­größen unterhalb von n0 mögen möglicher­weise Sonder­bedingungen gelten, so dass es auch hier nur auf das asymptotische Verhalten für ngrößer gleichn0 ankommt.

Interessant ist also wiederum nur die Größen­ordnung der unteren Schranke, d.h. ob es sich z.B. um eine lineare, quadratische oder exponentielle Funktion handelt. Die Größen­ordnung wird wieder durch eine Funktionen­klasse ausgedrückt.

Wie wir eben gesehen haben, liegt eine untere Schranke für das Sortier­problem in Ω(n). Eine obere Schranke liegt in O(n2), z.B. mit dem Sortier­verfahren 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 Sortier­verfahren Heapsort.

Definition:  Gegeben sei ein Problem und ein Algorithmus mit der Zeit­komplexitä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 Sortier­verfahren Heapsort ist daher optimal, da es die untere Schranke für das Sortier­problem erreicht.

 

Siehe auch:  [Obere und untere Schranken]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.03.1997   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik