O-Notation |
NixJava unregistriert
|
|
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.
|
|
29.04.2018 18:43 |
|
|
|