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

Aus Wikiversity

O-Notation[Bearbeiten]

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

Definition[Bearbeiten]

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.

Literatur[Bearbeiten]

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.