+26 Seien f,g : ℕ0 → ℝ mit f(n) = n^10 und g(n) = 2^n
Ich soll nun überprüfen ob:
(i) f ∈ O(g), (ii) f ∈ Ω(g), (iii) f ∈ Θ(g), (iv) f ∈ o(g), (v) f ∈ ω(g)
gelten. Und begründet Angeben.
Definitionen:
Aufgabe:
Ich verstehe die Definitionen nicht genau, bzw. die Aufgabe, die Landau-Symbole sind mir ein Rätsel..
Hilfe wäre super!
LG
+3976 Rein vom "Gefühl" her geht es hier ja darum, welche der Funktionen "schneller wächst". Intuitiv würden wir direkt sagen: 2n wächst schneller als n10. Nun müssen wir das irgendwie in den Definitionen umsetzen.
Zuerst sei festgehalten: Etwa für 58,7=n haben die Funktionen nochmal einen Schnittpunkt, es ist also g(58) < f(58) und g(59)>f(59). (Den kannst du durch Probieren oder einen passenden Schnittpunktrechner finden. Ist wahrscheinlich nicht zwingend nötig, den Schnittpunkt zu kennen, praktisch ist's aber wohl schon.)
So können wir direkt (i) und (iv) lösen indem wir n0 und c einfach angeben. Für beide passt n0=59 und c=1; denn nach dem Schnittpunkt liefert g einfach die größeren Werte.
Etwas schwieriger wird's bei (ii) und (v), denn hier wäre die Aussage, dass f schneller als g wächst, was ja nicht der Fall ist. Wir müssen also zeigen, dass die n0 und c aus der Definition nicht existieren. Wir betrachten die Ungleichung etwas genauer:
cg(n) < f(n)
c*2n < n10 |:n10; :c
\(\frac{2^n}{n^{10}} < \frac{1}{c}\)
Hier ist uns (hoffentlich) bekannt: die linke Seite geht für n gegen unendlich gegen 0. D.h. für jedes G>0 gibt es ein N0, sodass \(\frac{2^N}{N^{10}} > G\) für alle N>N0. Das zeigt uns: Egal wie wir c wählen, es gibt ein N0, ab dem die Ungleichung nicht mehr erfüllt ist. Deswegen kann es kein passendes n0 geben. (Für die Ungleichung mit \(\leq\) funktioniert's genauso.)
Damit ist auch (iii) direkt gelöst, denn nach (ii) existiert kein passendes c1.
Ich hab' mich da selbst immer ein bisschen auf meine Intuition verlassen, um zu entscheiden, ob ich passende n0 und c suche oder deren Existenz zu widerlegen versuche. Man merkt aber, wenn man auf der falschen Fährte ist, weils dann irgendwo immer schiefgeht. Vielleicht kannst du zu Übungszwecken versuchen zu zeigen, dass jedes Polynom ax3+bx2+cx+d in O(x3) (und o(x3)) ist.
