Algorithmische Geometrie
Komplexität & Effizienz
Von
Holger Jakusch
Ziel
 Notwendigkeit
 Unterschied: Komplexität /Effizienz
 Vorgehensweise
Inhalt
 Effizienz
 Notation
 Optimalität/ Komplexität
Warum?
 Vergleichbarkeit
 Abschätzung des Rechen- & Speicheraufwands
Effizienz
 Effizienz= Sparsamer Umgang mit Ressourcen
 Die Effiziens eines Algorithmus(für eine spezielle Eingabe)
kann man messen
 Kleine Datenmengen: Egal
 Große Datenmengen: Effizienz = Machbarkeit
 Laufzeiteffizienz/ Speichereffizienz
Effizienz
Beispiel: Effizientes & Uneffizientes Suchen
Uneffizient: Lineares Suchen: Suche nach 40
12
24
34
36
Laufzeit: f(n) = 2n
g(n)= n+1
40
47
63
Worst Case
Best Case
77
Effizienz
Allgemein:
 Abschätzung von Rechenzeit & Speicheraufwand
 Ahängigkeit:
f (n) Worst case
g(n) Average case
 Interessant für n →∞
 Numerische Konstanten sind uninteressant
 Art des Input
 Nicht: Millisekunde und Bit
 Elementaroperationen
Effizienz
Elementaroperationen:
 Vergleich zweier Zahlen
 Die 4 arithmetischen Operationen
 Normale Mathematische Funktionen
 Elementaroperationen im Beispiel
Elementaroperationen sind nicht festgelegt!
Effizienz
 Effizient: binäres Suchen Beispiel: Suche nach 40
12
24
34
36
 Laufzeit: f(n)= 1+log n
40
47
63
77
40
47
63
77
40
47
40
Effizienzklassen
 Warum Effizienz Klassen?
 Realisierung des Vergleiches zweier Algorithmen
 Welche Effienzklassen gibt es?
 Notation mit Hilfe der Landau- Symbole:O, Ω, Θ
Effizienzklassen
Klassifikation der Effizienz:
Asymptotisches verhalten
 log n, n, n log n, n², n³, … ,2ⁿ
 Langsam Steigend: log* n kleiner als 5 bis 265535
 Schnell steigend: Fakultät n!
Effizienzklassen
 Asymptotisches verhalten; Standart Effizienzklassen
300
250
200
log n
n
n log n
n²
n!
150
100
50
49
45
41
37
33
29
25
21
17
13
9
5
1
0
Landau Symbole
Im Fogenden: f und g seien zwei Algorithmen
und c eine Konstante
Landau Symbol: O
Obere Grenze für die die Effizienz eines
Algorithmus
 Gebräuchlich: f(n)= O(g(n)) n≥n0 f(n) ≤ cg(n)
 Math. korrekt:
fO(g):(c>0)(n0 N)(n ≥ n0) f(n) ≤cg(n)
 f(n) hat höchstens die Größenordnung g(n)
Landau Symbol: Ω
Untere grenze für die Effizienz eines Algorithmus
 Gebräuchlich:f(n)= Ω(g(n)) n≥n0 f(n) ≥ cg(n)
 Math. korrekt:
f Ω(g):g O(f)
 f(n) hat mindestens die Größenordnung g(n)
Landau Symbol: Θ
Untere & obere Grenze für die Effizienz eines
Algorithmus
 Gebräuchlich: f(n)= Θ(g(n)) n≥n0 c1g(n) ≤f(n) ≤c2(g(n))
 Math. korrekt:
f  Θ(g):(f  O(g) und f  Ω(g))
:(f  O(g) und g  O(f))
 f(n) hat die gleiche Größenordnung wie g(n)
Optimales Verhalten: Untere Grenzen
Wann heißt ein Algorithmus Optimal?
 Effizienz hat die gleiche Größenordnung wie die
Komplexität des Problems
 Optiemierung heißt: versuch Effizienz nahe an Komplexität
zu bringen
 Es ist wichtig, die Komlexität eines Problems zu kennen
Fazit
 Komplexität ist nicht gleich Effizienz
 Optimaler Algoritmus = Komplexität des Problems
 Komplexität hängt nicht nur von Größe, sondern auch von
dem Inhalt des Inputs ab
 Die Effizienz lässt sich im Verhältnis zum Input berechnen
 Probleme lassen sich durch bereits vorhandene Lösungen
darstellen
Ende
Fragen?

Komplexitätsanalyse und Effizienz