Auf dieser Seite werden die Komplexitätsklassen behandelt.

Wir sagen sei ${\displaystyle 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 ${\displaystyle f(n)\in O(p(n))}$. Des weiteren sagen wir, dass ein Algorithmus höchstens exponentielle Rechenzeit benötigt, falls es eine Konstante ${\displaystyle a\in \mathbb {R} ^{+}}$ gibt, mit ${\displaystyle f(n)\in O(a^{n})}$.

Die Komplexitätsklassen sind:

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

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

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

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

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

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.