O-Notation beispiele und Erklärung?
Hallo zusammen,
ich verstehe die O-Notation nicht genau, und wollte daher zu gegebenen Beispielen fragen, ob ich dies so richtig verstanden habe. Falls nicht, würde ich mich riesig über eine Erklärung freuen.
(Siehe Anhang)
Bei der ersten Aufgabe, ist es doch so, dass die Funktion höchstens so schnell wachsen darf, wie n hoch 7.
Wenn ich hier beispielsweise allerdings jegliche Zahl einsetze, so wächst es doch einwenig schneller als n hoch 7? So, dass dies nicht stimmen dürfte, oder?
Bei der zweiten Aufgabe darf die Funktion nur mindestens so schnell wachsen wie n hoch 7. Hier würde die Aussage doch zutreffen, da dies immer ein wenig höher ist, wenn man eine beliebe Zahl einsetzt, im Gegensatz zu n hoch 7, oder?
Bei der dritten Aufgabe darf die Funktion nur genau so schnell wachsen wie n quadrat.
Dies trifft allerdings nicht zu, oder?
Freue mich über jede Erklärung!
LG
Anhang
4 Antworten
a) Deine Erkenntnis ist richtig, die Funktion wächst schneller als n^7 Bei der O-Notation geht es aber darum, ob die Funktion langsamer wächst als a * n^7. Dies ist der Fall. Wähle als konstanten Faktor a beispielsweise 1000000 und du wirst sehen, dass die Funktion weniger schnell wächst als 1000000 * n^7. Und da du einen solchen konstanten Faktor a für n^7 findest, mit dem a * n^7 schneller wächst als die Funktion, liegt die Funktion in O(n^7). Dies muss übrigens nicht für x0=0 gelten. Es kann auch sein, dass a * n^7 die Funktion erst ab x0=10 oder so begrenzt.
Sind f(n) und g(n) zwei Funktionen, so sagt man:
- Wenn der Grenzwert von f(n)/g(n) für n gegen unendlich endlich ist, wachsen sie gleich schnell.
- Wenn der Grenzwert Null ist, so wächst g(n) schneller als f(n).
- Wenn der Grenzwert nicht endlich ist, wächst f(n) schneller als g(n).
Für |n| -> unendlich? (Es ist zwar anzunehmen, dass n als natürliche Zahl nicht gegen eine endliche reelle Zahl, insbesondere 0, streben kann, aber streng genommen muss es dazugesagt werden.)
Es geht hier um asymptotisches Verhalten, d. h. Größen, die im Verhältnis zum genannten Verhalten asymptotisch "schnell genug" verschwinden (in der Regel reicht jede - um einen noch so kleinen Wert - kleinere Ordnung aus), spielen keine Rolle.
Insbesondere ist (für |n| -> unendlich) O(n^k) + O(n^(k-1)) = O(n^k)
Entsprechend für Omega und Theta.
Du hast den Anhang vergessen.