Zum Inhalt springen

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

Aus Wikiversity




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.


Discussion