3. Kapitel: Komplexität und Komplexitätsklassen
Möglichkeit 1:
Hier: keine Formulierung der Alg. als RAM-Programme,
Beispiel: Maximum Subarray Problem
PPT-Folie
O-Notation:
Alternativdefinition Ottmann/Widmayer:
Leistungsverhalten bei kleiner Eingabegröße
Berechnung der (worst- case- ) Zeitkomplexität
Fallunterscheidung:
Zeitkomplexitätsklassen
Komplexitätsklassen P und NP
Definition: Nichtdeterminismus
P und NP als Wortproblem
Definition: deterministischer und nichtdeterministischer Algorithmus
Definition:
NP = { f: ?* ? ?* und f nichtdeterministisch polynomial-zeitberechenbar } heißt die Klasse der npzb-Funktionen.
Lösungsstrategien/Arten von Algorithmen
Divide and Conquer Methode
Anwendung auf Maximum Subarray Problem:
Damit erhält man folgenden D&C-Algorithmus:
Sei T(n) Anzahl der Schritte des Algorithmus bei Eingabe einer Folge der Länge n.
Noch besseres Verfahren: Scan-Line-Prinzip.
E-Mail: der@informatik.uni-leipzig.de
Homepage: http://www.informatik.uni-leipzig.de/~der