Kurs:Algorithmen und Datenstrukturen/Vorlesung/O-Notation




O-NotationBearbeiten

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ür Aufwandsfunktionen mit  

DefinitionBearbeiten

Für eine Funktion   ist die Menge   wie folgt definiert:

 

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:

 

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

LiteraturBearbeiten

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.