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

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

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.