Upload
nerice
View
23
Download
0
Embed Size (px)
DESCRIPTION
2. Kapitel: Komplexität und Komplexitätsklassen. Komplexität, O-Notation Relevante Eigenschaften von Algorithmen : Korrektheit, Terminierung, Komplexität Maße für Komplexität: benötigter Speicherplatz, benötigte Rechenzeit Schwierigkeit : abhängig von Rechner, Programmiersprache. - PowerPoint PPT Presentation
Citation preview
G.Heyer Algorithmen und Datenstrukturen1
2. Kapitel: Komplexität und Komplexitätsklassen
Komplexität, O-Notation
Relevante Eigenschaften von Algorithmen:Korrektheit, Terminierung, Komplexität
Maße für Komplexität:benötigter Speicherplatz,benötigte Rechenzeit
Schwierigkeit: abhängig von Rechner, Programmiersprache
G.Heyer Algorithmen und Datenstrukturen2
Möglichkeit 1:Definition eines idealisierten Modellrechners => RAM
(random access machine)• Befehlssatz ähnlich Assembler
(Laden, Speichern, arithmetische Verknüpfung von Registerinhalten, Sprünge),
• unendliche Menge von Speicherzellen, die natürliche oder reelle Zahlen speichern,
Speicherplatz => Zahl der benötigten RAM-ZellenLaufzeit => Zahl der ausgeführten RAM-Befehle
Möglichkeit 2:
Genaue Ermittlung bestimmter die Laufzeit charakterisierender Parameter(Beispiel: Sortieren -> Anzahl der Vergleichsoperationen)
G.Heyer Algorithmen und Datenstrukturen3
Hier: keine Formulierung der Alg. als RAM-Programme,
Abschätzung der Laufzeit mit Schwerpunkt Wachstum der Laufzeit in Abhängigkeit von Eingabegröße
Komplexität abhängig von Eingabegröße.
Einheitskostenmaß: nur Anzahl der Daten berücksichtigt (etwa Anzahl zu sortierender Zahlen)
log. Kostenmaß: auch Größe der Daten relevant (etwa Länge von Zahlen im Binärcode)
worst case, average case, best case Analysen, amortisierte Kosten
In der Regel genügt die Angabe der Größenordnung der Komplexität, wobei es auf konstante Faktoren nicht ankommt.
G.Heyer Algorithmen und Datenstrukturen4
O-Notation:Sei f: N -> R+ eine Funktion. Wir definieren:
O(f) = {g | c > 0 : n0 > 0 : n >= n0: g(n) <= cf(n)}
Beispiel:
3n4 + 5n3 + 7 log n O(n4), denn 3n4 + 5n3 + 7 log n < 3n4 + 5n4 + 7n4 = 15 n4 für n >= 1. Wähle also c = 15, n0 = 1.
In O(n4) steht n4 für die Funktion, die n auf n4 abbildet.Häufig schreibt man auch h = O(n4) statt h O(n4)
O macht Abschätzung nach oben, nach unten:
(f) = {g | c > 0 : n0 > 0 : n>= n0: g(n) >= cf(n)}
G.Heyer Algorithmen und Datenstrukturen5
Alternativdefinition Ottmann/Widmayer:
(f) = {g | c > 0 : unendlich vielen: g(n)>= cf(n)}
Beispiel: f(n) = 1 falls n gerade, n2 sonst.
Originaldefinition liefert f = (1), Alternativdefinition f = (n2).
Abschätzung von oben und unten (exakte Schranke)(f) = O(f) (f)
g aus (f) bedeutet also: die Funktion g verläuft ab einem Anfangswert n0 im Bereich [c1f,c2f] für geeignete Konstanten c1, c2.
G.Heyer Algorithmen und Datenstrukturen6
Berechnung der (worst- case- ) ZeitkomplexitätElementare Operationen (Zuweisung, Ein-/ Ausgabe) : O ( l )
Summenregel: T1 ( n ) und T2 ( n ) seien die Laufzeiten zweier
Programmfragmente P1 und P2 ; es gelte: T1 ( n ) O (f ( n ) ) und T2 ( n ) O ( g
( n ) ).
Für die Hintereinanderausführung von P1 und P2 ist dann T1 ( n ) + T2 ( n ) O ( max ( f ( n ), g ( n ) ) )
Produktregel: z. B. für geschachtelte Schleifenausführung von P1
und P2
T1 ( n ) * T2 ( n ) O ( f ( n ) * g ( n ) )
G.Heyer Algorithmen und Datenstrukturen7
Fallunterscheidung:Kosten der Bedingungsanweisung ( O ( l ) ) +
Kosten der längsten Alternative
Schleife:Produkt aus Anzahl der Schleifendurchläufe mit Kosten der teuersten Schleifenausführung
Rekursive Prozeduraufrufe: Produkt aus Anzahl der rekursiven Aufrufe mit Kosten der teuersten Prozedurausführung
G.Heyer Algorithmen und Datenstrukturen8
Zeitkomplexitätsklassen
Drei zentrale Zeitkomplexitätsklassen werden unterschieden:
Algorithmus A heißt:
linear-zeitbeschränkt fA O ( n )
polynomial-zeitbeschränkt k N, so daß
fA O ( nk ) .
exponentiell-zeitbeschränkt k N , so daß
fA O ( kn ).
G.Heyer Algorithmen und Datenstrukturen9
Komplexitätsklassen P und NPP: Die Menge aller Sprachen (Probleme), die ein deterministischer Automat in Polynomialzeit (O(P(n)) akzeptiert.
NP: Die Menge aller Sprachen (Probleme), die ein nicht-deterministischer Automat in Polynomialzeit löst.(Beispiel SAT)
G.Heyer Algorithmen und Datenstrukturen10
Definition: NichtdeterminismusAlgorithmus A heißt nichtdeterministisch, wenn A das
Sprachelement OR (in beliebiger Anzahl) enthält:
OR (Anw1, Anw2) bedeutet, daß entweder die Anweisung Anw1 oder die Anweisung Anw2 ausgeführt wird.
Die Auswahl zwischen den beidenAnweisungen ist willkürlich.
G.Heyer Algorithmen und Datenstrukturen11
P und NP als WortproblemEs sei A ein Algorithmus und die Eingabe von A ein Element aus * für ein Alphabet .
Für jedes Eingabewort w * sei
s(w) = Anzahl der Schritte bis zur Terminierung
sA(n) = maximale Schrittzahl, wobei
sA: 0 -> 0 mit
sA(n) = max {s(w)| mit w * , |w| =n}
G.Heyer Algorithmen und Datenstrukturen12
Definition: deterministischer und nichtdeterministischer Algorithmus
Ein deterministischer Algorithmus akzeptiert eine Sprache L in der Zeit O(f(n)), wenn der A. für jedes beliebige Wort w innerhalb der Zeitschranke f(|w|] entscheidet, ob w L gilt oder nicht.
Ein nichtdeterministischer Algorithmus akzeptiert eine Sprache L in der Zeit O(f(n)), wenn er für jedes Wort der Sprache L, das die Länge n besitzt, in O(f(n)) Schritten feststellt, dass das Wort zu der Sprache gehört.
CL heisst charakteristische Funktion von L * , wenn
TRUE falls w L
CL (w) = FALSE falls w L
G.Heyer Algorithmen und Datenstrukturen13
Definition:Eine Menge, Sprache oder ein Problem L heißt polynomial-zeitbeschränkt, wenn die charakteristische Funktion CL polynomial-zeitberechenbar ist.
Definition:
P = { L * : L polynomial-zeitbeschränkt }
heißt die Klasse der pzb-Sprachen.
NP = { L * : L nichtdeterministisch
polynomial-zeitbeschränkt }
heißt die Klasse der npzb- Sprachen.
P = { f: * * und f polynomial-zeitberechenbar }
heißt die Klasse der pzb-Funktionen
G.Heyer Algorithmen und Datenstrukturen14
NP = { f: * * und f nichtdeterministisch polynomial-zeitberechenbar }
heißt die Klasse der npzb-Funktionen.
Definitionen:
Seien L, L‘ *
a) L‘ heißt polynomial reduzierbar auf L
dund wenn es existiert eine pzb-Funktion
f: * * mit: w * w L‘ f ( w ) L
b) L heißt NP-schwierig
dund wenn für jedes L‘ NP gilt: L‘ ist polynomial
reduzierbar auf L.
c) L heißt NP-vollständig
dund wenn L NP und L ist NP-schwierig.
G.Heyer Algorithmen und Datenstrukturen15
Lösungsstrategien/Arten von Algorithmen
Kleine N: Beschränkte EingabegrößenTeile-und-Herrsche: Aufteilung eines Problems in Teilprobleme (die rekursiv gelöst werden können)Probabilistische A.: Optimierung der durchschnittlichen Kosten durch Annahmen über statistische Eigenschaften der Eingabe-größen(z.B. Randomisierung, Wahrscheinlichkeitshäufung)Approximierung: Errechnung einer hinreichend guten Lösung in einem beschränkten Suchraum(z.B. durch Heuristiken)Greedy Algorithms: Errechnung lokaler OptimaDynamische Programmierung: Aufteilung eines Problems in Teilprobleme und Wiederverwendung von Lösungen für Teilprobleme
G.Heyer Algorithmen und Datenstrukturen16
Leistungsverhalten bei kleiner EingabegrößeAsymptotische Komplexität gilt vor allem für große n
bei kleineren Problemen haben konstante Parameter wesentlichen Einfluß
Verfahren mit besserer ( asympt. ) Komplexität kann schlechter abschneiden als Verfahren mit schlechter Komplexität
T ( n ) Bereiche von n mit günstiger Zeitkomplexität
186182 log2 n n > 2048
1000 n 1024 <= n <= 2048
100 n log 2 n 59 <= n <= 1024
10 n2 10 <= n <= 58
n3 n = 10
2n 2 <= n <= 9