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 \mathbb {R} ^{+}{\text{für}}~0\leq i\leq m.~Dann~gilt~f(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 \mathbb {R} ^{+}$ 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(log~n)$	der logarithmische Aufwand
$O(n)$	der lineare Aufwand
$O(n\cdot log~n)$
$O(n^{2})$	der quadratische Aufwand
$O(n^{k})\ {\text{für}}\ k\geq 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(log~n)$	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 log~n)$	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.