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

Komplexitätsklassen

Auf dieser Seite werden die Komplexitätsklassen behandelt.

Wir sagen sei $f(n)=a_m\cdot n^m+a_{m-1}\cdot n^{m-1}+...+a_1\cdot n+a_0,wobei{a}_i\in {ℝ}^{+}\text{für}0\le i\le m.Danngiltf(n)\in O(n^m).$ Und wir sagen, ein Algorithmus mit Komplexität f(n) benötigt höchstens polynomielle Rechenzeit, falls es ein Polynom p(n) gibt, mit $f(n)\in O(p(n))$. Des weiteren sagen wir, dass ein Algorithmus höchstens exponentielle Rechenzeit benötigt, falls es eine Konstante $a\in {ℝ}^{+}$ gibt, mit $f(n)\in O(a^n)$.

Die Komplexitätsklassen sind:

$O(1)$	der konstante Aufwand, das bedeutet der Aufwand ist nicht abhängig von der Eingabe
$O(logn)$	der logarithmische Aufwand
$O(n)$	der lineare Aufwand
$O(n\cdot logn)$
$O(n^2)$	der quadratische Aufwand
$O(n^k)\text{für}k\ge 0$	der polynomiale Aufwand
$O(2^n)$	der exponentielle Aufwand

Wachstum

f(n)	n=2	$2^4=16$	$2^8=256$	$2^{10}=1024$	$2^{20}=1048576$
ldn	1	4	8	10	20
n	2	16	256	1024	1048576
$n\cdot ldn$	2	64	2048	10240	20971520
$n^2$	4	256	65536	1048576	$\approx 10^{12}$
$n^3$	8	4096	16777200	$\approx 10^9$	$\approx 10^{18}$
$2^n$	4	65536	$\approx 10^{77}$	$\approx 10^{308}$	$\approx 10^{315653}$

Zeitaufwand

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 $1\mu s=(10^{-6}s)$ 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	$6\cdot 10^7$	$3,6\cdot 10^9$	$8,6\cdot 10^{10}$	$6\cdot 10^{11}$	$3\cdot 10^{13}$
$n^2$	7750	$6\cdot 10^4$	$2,9\cdot 10^5$	$7,8\cdot 10^5$	$5,6\cdot 10^6$
$n^3$	391	1530	4420	8450	31600
$2^n$	25	31	36	39	44

Ein Beispiel ist für T=1 Min. : $1000\cdot 1000\cdot 60=6\cdot 10^7\mu s(10^{7}Schritte)$

Typische Problemklassen

Aufwand	Problemklasse
$O(1)$	für einige Suchverfahren für Tabellen (Hashing)
$O(logn)$	für allgemeine Suchverfahren für Tabellen (Baum-Suchverfahren)
$O(n)$	für sequenzielle Suche, Suche in Texten, syntaktische Analyse von Programmen (bei "guter" Grammatik)
$O(n\cdot logn)$	für Sortieren
$O(n^2)$	für einige dynamische Optimierungsverfahren (z.B. optimale Suchbäume), einfache Multiplikation von Matrix-Vektor
$O(n^3)$	für einfache Matrizen Multiplikationen
$O(2^n)$	für viele Optimierungsprobleme (z.B. optimale Schaltwerke), automatisches Beweisen (im Prädikatenkalkül 1.Stufe)

Literatur

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.