Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/O-Notation

O-Notation

Auf dieser Seite wird die O-Notation behandelt. Bei der O-Notation werden die asymptotischen oberen Schranke für Aufwandsfunktion angegeben. Das heißt deren Wachstumsgeschwindigkeit bzw. Größenordnung. Eine Asymptote ist eine Gerade, der sich eine Kurve bei immer größer werdender Entfernung vom Koordinatenursprung unbegrenzt nähert. Eine einfache Vergleichsfunktion ist $f(n)\in O(g(n))$ für Aufwandsfunktionen mit $g:\mathbb {N} \to \mathbb {N}$

Definition

Für eine Funktion $f:\mathbb {N} \to \mathbb {N}$ ist die Menge $O(f(n))$ wie folgt definiert:

$O(f(n))=\{g:\mathbb {N} \to \mathbb {N} |\exists c\in \mathbb {R} ^{>0},\exists n_{o}\in \mathbb {N} \ \forall n\geq n_{0}:g(n)\leq c\cdot f(n)\}$

Anschaulich formuliert bedeutet das, dass O(f(n)) die Menge aller durch f nach oben beschränkter Funktionen ist und somit die asymptotische obere Schranke ist.

Die Definition veranschaulichst sieht folgendermaßen aus:

$g(n)\in O(f(n))\Leftrightarrow \exists c>0,\exists n_{0}\forall n\geq n_{0}:g(n)\leq c\cdot f(n)$

Das heißt g wächst nicht schneller als f. Das bedeutet wiederrum ${\frac {g(n)}{f(n)}}$ ist für genügend große n durch eine Konstante c nach oben beschränkt.

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.2 zu finden.