Kurs:Algorithmen und Datenstrukturen/Vorlesung/Notation Komplexitätsklassen

Aus Wikiversity
Zur Navigation springen Zur Suche springen




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.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg