Geschrieben von NixJava am 29.04.2018 um 18:43:
ist die Stelle, ab der
die obere Schranke bildet. Das ist in der Grafik auch so angedeutet. Über das
muss nicht viel bekannt sein. Wichtig ist nur, dass es existiert.
Die Landau-Symbole abstrahieren das Laufverhalten asymptotisch. Das bedeutet, konstante Faktoren und Summanden können "gestrichen werden". So ist zum Beispiel
. Der Hintergedanke dieser Reduktion besteht darin, dass die genaue Laufzeit von der verwendeten Hardware abhängt. Durch eine größere Leistung kann ich den Algorithmus um einen konstanten Faktor beschleunigen.
Das
in der Definition übernimmt genau diese Rolle. In meinem obigen Beispiel kann ich
wählen und erhalte
. Für
gilt diese Gleichung nicht. Das muss sie auch nicht! Es reicht aus, wenn ein
existiert, so dass für alle
die Ungleichung erfüllt ist. Und so ein
existiert offensichtlich.