Landau-Symbole | Überprüfung , Asymptotische Notation

Question

Seien f,g : ℕ₀ → ℝ mit f(n) = n¹⁰ und g(n) = 2ⁿ

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:

Ich verstehe die Definitionen nicht genau, bzw. die Aufgabe, die Landau-Symbole sind mi ein Rätsel..

Hilfe wäre super!

Comments

Ich übersetze dir mal die Zeichen in einem Satz, in O(g) sind alle Funktionen f enthalten, definiert auf den natürlichen Zahlen in die reellen Zahlen mit der Eigenschaft, dass ein c>o und ein n aus N0 existiert, sodass für alle n>= n0 also alle natürlichen Zahlen die über dieser Schranke lieben, die entsprechende Ungleichung gelten muss

---

Wenn du die Symbole kennst. Kannst du für die anderen Mengen einen ähnlichen Satz formulieren, nur dass z. B das "für alle" mal dem "es existiert" weicht oder eine andere Ungleichung gelten muss

---

Und damit ist das wichtige: du musst die Ungleichung am Ende zeigen, aber je nach Menge für unterschiedliche Fälle: Z.b muss einmal die Ungleichung für alle c gelten und das andere mal musst du nur ein c finden.

---

ich versuche es mal, Danke!

---

Genau, falls du nicht weiter kommst, gib einfach bescheid. Und gerne :)

---

habe das in der Nacht nicht so gut hinbekommen, jetzt wo ich mich wieder drangesetzt habe verstehe ich nicht ganz wie die Notation jetzt aussehen soll, also wie genau schreibe ich das auf?

---

Mein ansatz für das erste:

n^10 ≤ c * n | :n

n^9 ≤ c → sol für alle n gelten deswegen Wiederspruch => n^10 ∉ O(g)

---

achso nein was rede ich hier, das ist ja Unsinn,

n^10 ≤ c * 2^n : 2^n

n^10/2^n ≤ c → soll für alle n gelten deswegen Wiederspruch => n10 ∉ O(g)

irgendwie so?

---

soll für alle n gelten deswegen Wiederspruch

Nein. Es soll für alle n ab einem gewissen Index n0 gelten. Da

$$ \frac{n^{10}}{2^n} \stackrel{n \to \infty}{\longrightarrow} 0 $$

Findest du für alle c > 0 ein solches n0.

---

Das verstehe ich nicht ganz.. tut mir leid

---

das was sie da gemacht haben gilt doch für klein o oder nicht`?

---

und ich verstehe absolut nicht wie ich die anderen zeige..

---

Vom Duplikat:

Titel: Nachweisen und Beweisen von Aufgaben

Stichworte: beweise,analysis

Aufgabe:

Seien \( f, g: \mathbb{N}_{0} \rightarrow \mathbb{R} \) mit \( f(n)=n^{10} \) und \( g(n)=2^{n} \). Überprüfen Sie, ob

(i) \( f \in O(g) \),
(ii) \( f \in \Omega(g) \),
(iii) \( f \in \Theta(g) \),
(iv) \( f \in o(g) \),
(v) \( f \in \omega(g) \)

gelten. Begrinden Sie Ihre Antworten.

Problem/Ansatz:

Weiß einer wie die Aufgabe machbar sind ?

Answer 1

Text erkannt:

(i) wible \( c=1 \) und \( n_{0}=100 \)
dann gitt \( n^{10} \leq 2^{n} \quad u_{n}=100 \)
(iv) Sa co0 und wille no so, dous
git \( \frac{u_{0}^{10}}{2^{10}}<c \Rightarrow n^{10}<2^{4} \cdot c \)
\( \Rightarrow \quad \frac{u^{\infty}}{z^{n}}<c \quad v_{n} \geq n_{0} \)

Hier sollte man noch definitiv hinschreiben, dass 2^n schneller wächst als n^10

Comments

Die Idee ist wie MatHaeMatician bereits beschrieben hat, dass 2^n "schneller wächst" als n^10 und deshalb immer 2^n ab einer bestimmten natürlichn Zahl n0 größer sein wird als n^10 egal welche konstante du vor 2^n schreibst. Das hat was mit Konvergenz zu tun, falls dir das noch nichts sagt. Die (iv) ist bei mir auch nicht ganz elegant gelöst, da am besten man nach n0 in Abhnägigkeit von c auflösen sollte, dies aber bei dieser Ungleichung nicht geht. Was du aber erkennen kannst ist, dass sich natürlich auch die Schranke n0 sich verändert je nach dem wie du c wählst, ist c klein gewählt so wir erst ab einer großen Schranke n0 die ungleichung erfüllt sein. Sie wird es aber definitiv.

---

hä aber bei iv muss ich doch nur das hier machen :

\( \lim\limits_{n\to\infty} \) n^10/2^n = 0

Da es = 0 ist kann man sagen dass n^10 ∈ o(2^n) ist oder nicht?

---

Korrekt, es klang aber für mich so als hättest du noch keine Konvergenz gehabt, deswegen habe ich strikt mit der Definition gearbeitet, die ja auch nichts anderes ist als die Definition der konvergenz

---

Okay wie i und iv funktionieren ist mir jetzt so in etwa klar, aber können sie mir noch den Rest erklären, finde auch nix genaueres dazu

---

Naja schau mal, wenn IV gilt, so kann nicht v gelten beispielsweise auf Grund deiner genannten Konvergenz. Ähnlich wirst du das dann auch bestimmt für die II zeigen können

Je nach dem wie genau du es begründen musst, bilde einfach die Negation der Aussage und zeige das dann

---

Dazu müsste ich die aussagen genauer verstehen, da drückt der Schuh nämlich

---

also v kann ich ausschließen, da durch die Konvergenz ja schon gezeigt wurde dass 2^n echt schneller wächst als n^10, kann ich das dann so als begründung schreiben also:

c * 2^n < n^10 → trifft nicht zu aus iv

---

für (ii)

mein c ≥ n^10/2^n

somit stimmt doch die aussage aus groß Omega also:

0 ≤ c * 2^n ≤ n^10

da c eine Nullfolge ist und g mit dieser multipliziert wird und somit das gesamte eine nullfolge wird, und somit f größer gleich ist? Kann das so richtig sein?

Also somit ist dann auch

f ∈ Ω(g)