Geschrieben von NixJava am 29.04.2018 um 18:43:
![[latex]n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_0)
ist die Stelle, ab der
![[latex]f[/latex]](http://www.matheboard.de/latex2png/latex2png.php?f)
die obere Schranke bildet. Das ist in der Grafik auch so angedeutet. Über das
![[latex]n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_0)
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
![[latex]4n^2 + 3 \in O(n^2)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?4n^2 + 3 \in O(n^2))
. 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
![[latex]c[/latex]](http://www.matheboard.de/latex2png/latex2png.php?c)
in der Definition übernimmt genau diese Rolle. In meinem obigen Beispiel kann ich
![[latex]c=5[/latex]](http://www.matheboard.de/latex2png/latex2png.php?c=5)
wählen und erhalte
![[latex]4n^2 + 3 \le 5n^2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?4n^2 + 3 \le 5n^2)
. Für
![[latex]n=1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n=1)
gilt diese Gleichung nicht. Das muss sie auch nicht! Es reicht aus, wenn ein
![[latex]n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_0)
existiert, so dass für alle
![[latex]n \ge n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n \ge n_0)
die Ungleichung erfüllt ist. Und so ein
![[latex]n_0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?n_0)
existiert offensichtlich.