Asymptotische Analyse

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ...

Übersicht: Asymptotische Analyse

Definition Komplexität

Die Komplexität eines Algorithmus oder einer Funktion bezeichnet die Wachstumsrate von Ressourcen wie zum Beispiel der Laufzeit gegenüber der Menge der zu verabeitenden Daten.

Wir unterscheiden zwischen:
Im folgenden wird verstärkt auf die Laufzeitanalyse eingegangen. Die Vertiefung der Speicherplatzkomplexität erfolgt im letzten Kapitel.


[ nach oben ]

Definition Ordnung

Ordnung (order notation) ist ein mathematisches Verfahren zur Einordnung der Komplexität von Funktionen. 

geg.: zwei Funktionen f,g
      eine positive Konstante C (Proportionalitätskonstante)
      eine natürliche Zahl n0

  1. O-Notation (big O-notation) - stellt eine obere Schranke für die Funktion f dar

    f hat höchstens den Grad g
    f = O(g), wenn gilt: f(n) ≤ C g(n), ∀ n0 ≥ n


  2. Ω-Notation (Ω-notation) - stellt eine untere Schranke für die Funktion f dar

    f hat mindestens den Grad g
    f = Ω(g), wenn gilt: f(n) ≥ C g(n), ∀ n0 ≥ n


  3. Θ-Notation (Θ-notation) - gibt eine exakte Einschätzung des Grades an

    f hat exakt den Grad g
    f = Θ(g), wenn gilt: f(n) = O(g) ∧ f(n) = Ω(g),
    also C1 g(n) ≤ f(n) ≤ C2 g(n), ∀ n0 ≥ n

Alle Definitionen gehen davon aus, dass wir nur positive Ergebnisse für f und g betrachten. Das "="-Zeichen ist hier nicht mit der arithmetischen Definition von "=" zu verwechseln. O, Ω und Θ stellen vielmehr Mengen dar, die alle Funktionen enthalten, für die eine Konstante C existiert und die die entsprechenden Ungleichungen für O, Ω und Θ erfüllen.

Häufig anzutreffende Komplexitäten:

Hinweise zur Berechnung
O(n) beschreibt stets das Verhalten einer anonymen Funktion f. Wenn wir auf Gleichungen wie z.B. O(n) + O(n) treffen, sind dort implizit f1(n) und f2(n) referenziert. Das Ergebnis muss also O(n) = O(n) + O(n) = f1(n) + f2(n) lauten.

Ein Ausdruck wie bedeutet nicht .

Statt dessen referenziert O(n2) wieder eine einzelne anonyme Funktion f, die den Ansprüchen f(n) = O(n2) genügt. Korrekt lautet das Ergebnis einer solchen Rechnung:


Konstanten spielen in der Betrachtungen der Komplexität eine untergeordnete Rolle. Es ist das Ziel unserer Bemühungen, Ausdrücke zur Charakterisierung der Funktionen möglichst simpel zu gestalten. Deshalb ist ein Ausdruck wie O((n2 / a) * b) nicht falsch, aber sinnvoller ist es den Ausdruck zu vereinfachen: O(n2).


[ nach oben ]

Darstellung einer Laufzeitanalyse

Ist eine Funktion f gegeben werden wir die Darstellung T(f)(n) nutzen, um eine asymptotische Abschätzung der Anzahl der notwendigen Reduktionsschritte zu geben. n charakterisiert dabei die Größe des übergebenen Arguments. Des weiteren wird die Eager Evaluation als Auswertungsgrundlage genutzt. Wir verwenden nicht die Lazy Evaluation um Ausdrücke zu reduzieren, weil es bei gewissen Audrücken schwierig ist, eine genaue Abschätzung zu geben. Ein Beispiel ist folgende Definition:

minlist = head . sort

Nutzen wir die Eager Evaluation zur Auswertung, ist die Berechnung kompositionell möglich (mit n Länge der Liste):

T(minlist)(n) = T(sort)(n) + T(head)(n)

Unsere Vorgehensweise um minlist zu berechnen ist: Liste sortieren in T(sort)(n) Reduktionsschritten, dann den Kopf der Liste in T(head)(n) Schritten ermitteln. Diese Gleichung ist in der Lazy Evaluation nicht gültig, da wir nicht mit Bestimmtheit sagen können, dass wir sort xs, um den Kopf der Liste zu ermitteln, in Normalform transformieren müssen. Die zeitliche Analyse unter der Eager Evaluation ist einfacher und kompositionell. Es gelten weiterhin die Gesetze, die im ersten Kapitel erarbeitet worden:


[ nach oben ]

Beispiel: reverse

Im folgenden Beispiel werden zwei verschiedene Definitionen einer Funktion reverse analysiert. reverse dreht eine übergebene Liste um. Beide Funktionen liefern das gleiche Ergebnis, besitzen aber deutliche Unterschiede in ihrer Laufzeit. 

 01  reverse1 []       = []
 02  reverse1 (x:xs)   = reverse1 xs ++ [x]
 03  
 04  reverse2          = foldl prefix []
 05                    where prefix xs x = x : xs


Betrachten wir zuerst die Laufzeit von reverse1. 
T(reverse1)(0)      = O(1) = Θ(1)
T(reverse1)(n+1)    = T(reverse1)(n) + T(++)(n,1)

Die Aussage der ersten Gleichung ist, dass wir eine konstante Laufzeit zur Umkehrung einer leeren Liste benötigen. Die zweite Gleichung setzt sich aus der Laufzeit zusammen, die für die Drehung einer Liste der Größe n benötigt wird und die Laufzeit um eine ein-elementige Liste mit einer n-elementigen Liste zu konkatenieren. Eine Laufzeituntersuchung von T(++)(n,1) ergibt T(++)(n,1) = Θ(n), da T(++)(n,m) = Θ(n). Als Zwischenergebnis unserer Berechnung erhalten wir: 
T(reverse1)(n+1)    = T(reverse1)(n) + Θ(n)

Führen wir nun die Rekursion T(reverse1)(n) durch erhalten wir Summierung:

reverse1 besitzt also eine Laufzeitkomplexität Θ(n2)


Bevor wir mit der Laufzeitanalyse für reverse2 beginnen können, müssen wir die fold-Funktion aus der Definition eliminieren, um eine direkte Rekursion zu erhalten. Dazu führen wir die Hilfsfunktion accum ein. 

 01  reverse2          = foldl prefix []
 02                    where prefix xs x = x : xs
 03  
 04  -- neue Definition mit accum
 05  reverse2 xs       = accum [] xs
 06  accum ws []       = ws 
 07  accum ws (x:xs)   = accum (x:ws) xs

Die Funktionsweise von accum wird nach der Bearbeitung des vierten Kapitels "Parameter Akkumulation" deutlicher. Wir übergeben accum initial eine Ergebnisliste (leere Liste) und eine Quellliste. accum fügt rekursiv das aktuelle Element der Quellliste vorne an die Ergebnisliste an, bis die Quellliste komplett bearbeitet ist.

Laufzeituntersuchung reverse2: 
T(reverse2)(m,0)      = O(1) = Θ(1)
T(reverse1)(m,n+1)    = O(1) + T(accum)(m,n)
m entspricht der Länge der Ergebnisliste und ist für die Laufzeit irrelevant. n entspricht der Länge der Quellliste. Wie man deutlich an der zweiten Gleichung erkennt stehen Länge der Quellliste und Laufzeit in einem linearem Verhältnis zueinander. Die Laufzeit beträgt daher: Θ(n). Die O(1) Komplexität in der zweiten Gleichung gibt die cons-Operation wieder.


[ nach oben ]

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ... [ nach oben ] ...