Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das... :: Thema anzeigen

Achtung: Dies ist eine historische Web-Site. Aktuell ist https://rainer.gerhards.net/ (engl) bzw https://www.rainer-gerhards.de/ (deutsch). Alle dynamischen Funktionen, Formulare etc auf dieser Seite sind abgeschaltet.
Datenschutzerklärung Impressum

Astronomy and Space Flight, Astronomie und Raumfahrt und dies und das...

Mathematik - Landau Symbole (u. a. "big O")

rgerhards - 15.10.2008, 15:46 Uhr
Titel: Landau Symbole (u. a. "big O")

Die Landau-Symbole haben in der Informatik eine wichtige Bedeutung. Sie werden beispielsweise zur Abschätzung der Laufzeit von Algorithmen oder auch der Kosten von Schaltungen verwendet.

Ein guter Artikel findet sich bei Wikipedia: http://de.wikipedia.org/wiki/Landau_Symbole

Examplarisch sei hier ein Beispiel (aus dem Kurs-Skript) gezeigt:

$3n^2 - 4n +5 \in O(n^3)$

Das sagt folgendes: wenn Du Dir

plotten lässt und n^3

, dann wirst Du feststellen, dass die erste Funktion nicht wesentlich schneller wächst als die zweite. Das sieht so aus:

Genau genommen wächst sie also sogar langsammer, ist also o(n^3)

("little o"), was aber im Skript nicht eingeführt wurde.

In der Praxis wird meist anstelle von

$3n^2 - 4n +5 \in O(n^3)$

die Schreibweise mit Gleichheitszeichen verwendet:

3n^2 - 4n +5 = O(n^3)

Dies ist zwar üblich, aber mathematisch nicht korrekt. Insbesondere darf man sich dadurch nicht verleiten lassen, mit zwei solcher Landau-Symbole zu rechnen.