Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Notation Komplexitätsklassen
Komplexitätsklassen
[Bearbeiten]Auf dieser Seite werden die Komplexitätsklassen behandelt.
Wir sagen sei Und wir sagen, ein Algorithmus mit Komplexität f(n) benötigt höchstens polynomielle Rechenzeit, falls es ein Polynom p(n) gibt, mit . Des weiteren sagen wir, dass ein Algorithmus höchstens exponentielle Rechenzeit benötigt, falls es eine Konstante gibt, mit .
Die Komplexitätsklassen sind:
der konstante Aufwand, das bedeutet der Aufwand ist nicht abhängig von der Eingabe | |
der logarithmische Aufwand | |
der lineare Aufwand | |
der quadratische Aufwand | |
der polynomiale Aufwand | |
der exponentielle Aufwand |
Wachstum
[Bearbeiten]f(n) | n=2 | ||||
ldn | 1 | 4 | 8 | 10 | 20 |
n | 2 | 16 | 256 | 1024 | 1048576 |
2 | 64 | 2048 | 10240 | 20971520 | |
4 | 256 | 65536 | 1048576 | ||
8 | 4096 | 16777200 | |||
4 | 65536 |
Zeitaufwand
[Bearbeiten]Nun stellen wir uns die Frage, wie groß bezüglich der Rechenschritte darf, oder kann ein Problem sein, je nach Komplexitätsklasse, wenn die Zeit T begrenzt ist? Wir nehmen an, dass wir pro Schritt eine Rechenzeit von brauchen. In der folgenden Tabelle steht T für die Zeitbegrenzung und G für die maximale Problemgröße.
G | T=1Min. | 1 Std. | 1 Tag | 1 Woche | 1 Jahr |
n | |||||
7750 | |||||
391 | 1530 | 4420 | 8450 | 31600 | |
25 | 31 | 36 | 39 | 44 |
Ein Beispiel ist für T=1 Min. :
Typische Problemklassen
[Bearbeiten]Aufwand | Problemklasse |
---|---|
für einige Suchverfahren für Tabellen (Hashing) | |
für allgemeine Suchverfahren für Tabellen (Baum-Suchverfahren) | |
für sequenzielle Suche, Suche in Texten, syntaktische Analyse von Programmen (bei "guter" Grammatik) | |
für Sortieren | |
für einige dynamische Optimierungsverfahren (z.B. optimale Suchbäume), einfache Multiplikation von Matrix-Vektor | |
für einfache Matrizen Multiplikationen | |
für viele Optimierungsprobleme (z.B. optimale Schaltwerke), automatisches Beweisen (im Prädikatenkalkül 1.Stufe) |
Literatur
[Bearbeiten]Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 7.3.3 zu finden.