Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Version: WS 18/19
Prof. Dr. Volker BlanzLehrstuhl für Medieninformatik Universität Siegen – Fakultät IV
Algorithmen und Datenstrukturen
Algorithmen und Datenstrukturen
10 Aufwand von Algorithmen
10.1
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10 Aufwand von Algorithmen ...
Motivation:
In der Regel gibt es viele mögliche Algorithmen um ein Problem zu lösen
Frage: Welcher Algorithmus ist ,,der Beste“?
Gebraucht werden Methoden zur
Bewertung des Aufwands von Algorithmen hinsichtlich Speicherplatz
Bewertung des Aufwands von Algorithmen hinsichtlich Laufzeit
Klassifikationen von (vergleichbaren) Algorithmen
Herausforderungen:
Basis ist eine mathematisch abstrakte Sichtweise
Literatur: Neben den Einträgen in [Claus]
[Ernst] Abschnitt 10.2
[Gumm] Abschnitt 4.1.4
[Herold] Abschnitt 8.4.4
[Cormen] Kap. 2 (in der englischen Ausgabe)
10.2
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.1 Einleitung
Aufgabe: Allgemeine Bewertung des notwendigen Aufwands zur Bearbeitung
eines Problems oder eines Algorithmus in Abhängigkeit vom Umfang
der Eingabedaten
⇒ Vergleichbarkeit von Algorithmen zur Lösung eines Problems
⇒ Bewertung, ob Probleme überhaupt in sinnvoller Zeit gelöst werden können
Aufwand eines Algorithmus beschreibt dessen Resourcenbedarf:
Speicherbedarf: Wieviel Arbeitsspeicher benötigt ein Algorithmus?
Zeitbedarf: Wie lange benötigt ein Algorithmus zur Problemlösung?
Komplexität eines Problems beschreibt den minimalen Resourcenbedarf
aller Algorithmen, die das Problem lösen
⇒ Theoretisch müssen alle möglichen Algorithmen, die ein Problem
lösen, betrachtet werden
Dies ist die Fragestellung der Komplexitätstheorie
Unser Fokus: Bewertung des Zeitaufwands eines Algorithmus
10.3
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.1 Einleitung ...
Speicherbedarf von Algorithmen (Speicherkomplexität)
Wenn ein Programm ausgeführt wird, benötigt es Speicher
Der Speicheraufwand setzt sich zusammen aus
Speicherplatzbedarf für das ausführbare Programm
dynamisch allokierten Speicher bei der Ausführung
Die Abhängigkeit des Speicherplatzbedarfs von den Eingangsdaten bezeichnet
man als Speicherkomplexität
10.4
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.2 Laufzeit von Algorithmen (Laufzeitkomplexität)
Konkrete Rechenzeit eines Algorithmus hängt von vielen Faktoren ab:
Rechnertyp (CPU, RAM, etc.) und Betriebssystem
Compiler und Rechnerauslastung zur Laufzeit
Anzahl und konkreter Inhalt der Eingangsgrößen
vom konkreten Algorithmus (Anzahl elementarer Operationen etc.)
konkrete Laufzeit in ms ist kein geeignetes Vergleichskriterium
Zeitkomplexität (Laufzeit) betrachtet
Zentrale Frage ist also vereinfacht:
Anzahl der Operationen in Abhängigkeit vom Umfang der Eingabedaten
Wieviele Operationen werden ausgeführt, wenn die Anzahl der
Eingabedaten verdoppelt, halbiert oder anderweitig verändert wird?
10.5
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.2 Laufzeit von Algorithmen (Laufzeitkomplexität) ...
Elementare Kosten
Frage: Was zählt als Operation und wie werden sie bewertet?
Operation sind Rechenschritte, die vereinfacht wie folgt bewertet werden:
Operation Bewertung
elementare Arithmetik 1
(Addition, Multipl., Modulo)
Vergleich 1
Wertzuweisung 1
Schleifen Kosten für m Durchläufe: Initialisierung,
(for, while, do-while) mAbbruchvergleich, mWeiterzählungund mKosten Schleifeninhalt
Bedingte Ausführung (if) Kosten des logischen Ausdrucks + maximaleKosten beider Zweige
Funktionsaufrufe Kosten der Operationen in der Funktion
10.6
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.2 Laufzeit von Algorithmen (Laufzeitkomplexität) ...
Beispiel: Polynomauswertung
Ziel: Auswertung eines Polynoms n-ten Grades
(Primitive!) Implementierung in Pseudo-Code-Form
float a[n+1] = ... ; // Koeffizienten a_ifloat x = ...; // Parameterfloat power; // x^kfloat result = 0; // Initialisierungint i,j;
for ( i = 0; i <= n; i ++ ) // Schleife ueber Koeff.power = 1;for ( j = 1; j <= i; j ++ ) // Schleife fuer x^i
power *= x;result += a[i] * power;
return result;
( ) 011
1 axaxaxaxp nn
nn ++++= -
- !
10.7
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.2 Laufzeit von Algorithmen (Laufzeitkomplexität) ...
Bewertung der Kosten:result = 0; 1+
for (i = 0; 1 +
i <= n; (n+1) + [ n+1 Durchläufe ! ]
i ++ ) (n+1) +
power = 1; 1+
for (j = 1; 1 +j <= i; i +j ++ ) i +
power ∗ = x; 2)+ (power=power * x)
result += a[i] ∗ power 3) (r = r + a * power)
(i=0
n
∑
(j=1
i
∑
10.8
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.2 Laufzeit von Algorithmen (Laufzeitkomplexität) ...
Zusammengefasst ergibt sich ein funktionaler Zusammenhang zwischen
dem Grad n und der Anzahl Operationen (Laufzeitkomplexität) T(n):
( ) ( ) ( )å=
+++=+++++=
n
i
nnniinnT0 2
1479322224
992 2 ++= nn
10.9
( )å=
+=
n
i
nni0 2
1mit
T n( ) =1+1+ 2(n+1)+ 1+1+ 2i+ 2j=1
i
∑"
#$$
%
&''+3
"
#$$
%
&''
i=0
n
∑
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.2 Laufzeit von Algorithmen (Laufzeitkomplexität) ...
Bemerkung:
Die vereinfachende Annahme, dass alle Operationen dieselbe konstante
Zeit c benötigen, ist eine (fehlerbehaftete) Annäherung
Beispiel: Eine Multiplikation benötigt in der Regel mehr Zeit als eine Addition
u.U. werden mehrere Eingangsgrößen (z.B. n und m) in die Laufzeitbetrachtung einbezogen. Dann ergibt sich für die Laufzeit z.B. eine Funktion T(n,m).
in der Praxis werden häufig nicht alle Operationsarten berücksichtigt,
insbesondere Zuweisungen und (Schleifen-)Initialisierungen werden häufig vernachlässigt
10.10
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.2 Laufzeit von Algorithmen (Laufzeitkomplexität) ...
Beispiel: Alternative Polynomauswertung nach dem Horner-Schema
Bisherige Polynomauswertung ist nicht ideal und braucht viele Operationen
Alternativer Algorithmus: Horner-Schema
( ) ( )( )( )( !! nn xaaxaxaxaxaxp ++++++= -13210
Implementierung (in Pseudo-Code-Form)
float a[n+1] = ... ; // Koeffizienten a_ifloat x = ...; // Parameterfloat result = a[n]; // Initialisierung 1 +int i;for ( i = n; i > 0; i -- ) // Schleife über Koeffizienten 1 + n(1+1
result *= x; +2result += a[i-1]; +2)
Laufzeitkomplexität des Horner-Schemas: T(n) = 2 + 6n
10.11
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.3 Asymptotische Komplexität und O-Notation
Vergleich der beiden Algorithmen zur Auswertung von Polynomen:
( ) 992 2 ++= nnnT
Algorithmus Polynomgrad n =2 4 8 16 32 64
Primitive Implementierung 35 77 209 665 2345 8778
Horner Schema 14 26 50 98 194 386( ) 26 += nnT
Beobachtung: Nicht alle Terme in T(n) sind gleich relevant
Beispiel: n2-Anteil ist für große n für T(n) = 2n2 + 9n + 9 dominierendAsymptotische Laufzeit: Betrachtung der Laufzeitkomplexität, wenn der
Umfang der Eingangsdaten gegen unendlich geht⇒Nur die dominanten Anteile werden berücksichtigt!Frage: Wie verhält sich T(n) für große n qualitativ
Konkret: Die primitive Implementierung verhält sich quadratisch (n2 dominant),das Horner Schema linear (n dominant)
10.12
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.3 Asymptotische Komplexität und O-Notation ...
O-Notation (Landau-Notation)
Ziel: Beschreibung des asymptotischen Verhaltens von Algorithmen, also insbesondere
der dominanten Terme
Definition:
Sei f(n) die Komplexitätsfunktion zur Beschreibung der Laufzeit eines
Algorithmus, abhängig von der Eingangsgröße n ∈ ℕ
Sei g(n) eine weitere Funktion (Grundfunktion), dann ist f von der
Ordnung von g, wenn
∃Konstante c > 0 : ∃n0 ∈ N :∀n > n0 : f n( ) ≤ c ⋅ g n( )
Zeichen:
Sprich: ,,f ist von der Ordnung Groß-O von g
O wird auch Landau-Symbol genannt
( ) ( )( )ngOnf Î
10.13
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.3 Asymptotische Komplexität und O-Notation ...
Beispiel: O-Notation
( ) ( ) nnnnnnncnOnnf +=£+>"==Î+= 4514::2,5,14.1 00für denn
Bemerkung:
es kommt nicht darauf an, den kleinstmöglichen Startwert n0 oder diekleinstmögliche Konstante c zu finden. Es zählt nur, dass irgendwelche n0 und c existieren.
O(g) definiert für die Grundfunktion g die Menge der Funktionen der Ordnungvon g
( ) ( ) ( ) ( ) ( )hOgOhOfhOggOf ÍÎÞÎÙÎ also:gilt Es ,
( ) ( ) 2200
22 1::0,1,1.2 nnnnncnOnnf £->"==Î-= für denn
( ) ( ) ( )( )( ) ( )nnnnnnn
ncnnOnnnnf
log21log2:
:12,log1log2.3
0
0
<+->"
==Î+-= undfür denn
( ) ( ) ( ) ( )21 nOnngnOnnf Î=ÙÎ-=:Beispiel
es ist stets die kleinste Menge von Interesse, der f gerade noch zugehört.
10.14
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.3 Asymptotische Komplexität und O-Notation ...
Weitere asymptotische Schranken
O(g(n)) legt eine obere Schranke für das Wachstum fest
Untere Schranke für das Wachstum einer Funktion f (Groß-Omega-Notation)
Exakte Schranke für das Wachstum einer Funktion f (Groß-Theta-Notation)
f ∈Ω g( ) :⇔∃Konstante c:∃n0 ∈ N :∀n ≥ n0 : f n( ) ≥ c.g n( )
f ∈Θ g( ) :⇔∃Konstante c1 ,c2 :∃n0 ∈ N :∀n ≥ n0 :
( ) ( ) ( )ngcnfngc ×££× 21
( )ngc ×
( )nf( )nf
( )ngc ×
( )nf( )ngc ×2
( )ngc ×1nn nObere Schranke Untere Schranke Exakte Schranke
10.15
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.4 Komplexitätsklassen
Ziel: Geeignete Grundfunktionen zur Klassifikation der (Laufzeit-)Komplexität
Übliche Komplexitätsklassen:
Klasse Die Anzahl der Operationen
O(1) ist unabhängig von der Eingangsgröße nO(log(n)) wächst logarithmisch mit der Eingangsgröße nO(n) wächst linear mit der Eingangsgröße nO(n log(n)) wächst linear-logarithmisch mit der Eingangsgröße nO(n2) wächst quadratisch mit der Eingangsgröße nO(n3) wächst kubisch mit der Eingangsgröße nO(nm),m ∈ ℕ wächst polynomiell mit nO(kn) wächst exponentiell mit der Eingangsgröße nO(n!) wächst gemäß der Fakultät der Eingangsgröße n
( ) ( )( ),
loglog2
2
alogxxa =
Hinweise: Die Klassen sind nach aufsteigender Komplexität sortiert
Für logarithmische Komplexität ist die Basis unerheblich, da
d.h. sie unterscheiden sich nur durch eine Konstante
10.16
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.4 Komplexitätsklassen …
Verhalten der Grundfunktion gFrage: Was sagt es aus, dass ein Algorithmus in einer bestimmten Komplexitätsklasse liegt (,,Die nächste Rechnergeneration ist sowieso 2x schneller!)?
Beispiele für die Rechenzeit bei 2ns Taktzeit (500MHz-Rechner)
O(log(n)) 2ns 4ns 6ns 8ns 10ns 12ns 14nsO(n) 4ns 8ns 16ns 32ns 64ns 128ns 256nsO(n log(n)) 4ns 16ns 48ns 128ns 120ns 768ns 1792nsO(n2) 8ns 32ns 128ns 512ns 2μs 8μs 32μsO(n3) 16ns 128ns 1μs 8μs 65μs 524μs 4msO(2n) 8ns 32ns 512ns 131μs 8.59s 1169a 2·1022aO(3n) 18ns 162ns 13μs 86ms 42.89d 2·1014a 7.5·1044aO(n!) 4ns 48ns 81μs 11.6h 1.67·1028a 1.9·1074a 2·10214a
Wert von nKlasse 2 4 8 16 32 64 128
10.17
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.4 Komplexität von Schleifen
for (i=1; i<=n; i++) cout << i << “ ,”; // dieser Schleifenrumpf umfasse c Schritte
-> 1, 2, 3, 4, 5. O(n)
for (i=1; i<=n; i++) for (k=1; k<=n; k++)
cout << “(“ << i << “ ,” << k << “) ,”;
-> (1,1) (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,2), , O(n2).
for (i=1; i<=n; i++) for (k=1; k<=i; k++) . // dies ist der häufiger auftretende Fall
cout << “(“ << i << “ ,” << k << “) ,”;
-> (1,1) , (2,1), (2,2), (3,1), (3,2), (3,3),
also ebenfalls O(n2).
!"#$
%!&#$
"' = !
"#$
%) * ' = ' *!
"#$
%) = ' * + * + + 12 = '
2 * +/ + '
2 * +
!"#$
%' = + * '
!"#$
%!&#$
%' =!
"#$
%+ * ' = + * + * '
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.4 Komplexität von Schleifen
Bei 3 geschachtelten Schleifen hätten wir O(n3).
Wir sehen:• m geschachtelte Schleifen mit je n Durchläufen führen zu O(nm)• In Bezug auf die Komplexitätsklasse macht es keinen Unterschied, ob alle Schleifen bis
n laufen, oder ob die inneren Schleifen jeweils nur bis zum Wert der jeweils anderen laufen wie in
for (i=1; i<=n; i++) for (k=1; k<=i; k++)
...
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.4 Komplexitätsklassen …
Abschätzungsregeln
Frage: Wie kann man die Komplexitätsklasse eines Algorithmus abschätzen?Grundregeln: m verschachtelte Schleifen der Länge n: O(nm) (polynomiell) lineare Rekursion (max. Aufruftiefe n): O(n) (linear) baumartige Rekursion (max. Aufruftiefe n, m Unteraufrufe): O(mn) (exponentiell)
Beispiel: Fibonacci Zahlen
Rekursive Implementierung: O(2n)
int fib(int n)if (n == 0)
return 0;else
if (n == 1) return 1;
else return fib(n-1) + fib(n-2);
Iterative Implementierung: O(n)
int fib(int n)int fib[3] = 0, 1, 1;
if (n <= 2) return fib[n];
while ( n-- >= 3 ) fib[0] = fib[1];fib[1] = fib[2];fib[2] = fib[0] + fib[1];
return fib[2];
10.20
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.4 Komplexitätsklassen …
Komplexitätstheorie
...ist eine eigene Disziplin in der Informatik
...befasst sich u.a. mit weitergehenden Fragen wie
Beweis von Problem-Komplexität (statt Algorithmen-Komplexität)
Lösbarkeit von Problemen
Weitere Komplexitätskategorien: Bestimmung der Laufzeit im
worst-case: Aufwand im schlimmsten Fall (unser Ansatz)
average-case: Aufwand im durchschnittlichen Fall
best-case: Aufwand im besten Fall
Average-Case: Ebenso wichtig wie der worst-case, aber schwerer ermittelbar
10.21
Prof. Dr. Volker BlanzFachgruppe Medieninformatik
Algorithmen und Datenstrukturen
10.5 Zusammenfassung
Wichtige Erkenntnisse und Inhalte dieses Abschnitts:
Zielsetzung: Vergleich von Algorithmen hinsichtlich ihres AufwandsUnser Fokus: Laufzeit
Erkenntnis: Abstraktion von realer Laufzeit notwendig
Laufzeitkomplexität T(n) beschreibt die Anzahl der Operationen inAbhängigkeit des Umfang der Eingangsgröße n
Asymptotische Komplexität beschreibt das qualitative Verhalten inAbhängigkeit von n
Asymptotische Schranken: Untere (Ω), obere (O) und exakte Schranke
Komplexitätsklassen: ,,Bewährte Grundfunktionen für asymptotische Schranken
Q
10.22