O-Notation /-Landau Notation beweisen oder widerlegen

Question

Frage:

Ich soll folgende zwei Aussagen untersuchen, ob sie korrekt sind und ggf. widerlegen.

1. (2n^2)^2 ∈ Ο (4^n)

2. (3 ln n^3)^3 ∈ o (1/3 3√n)   (3.Wurzel aus n)

Wie mache ich das am besten? Vielen Dank im Voraus. :)

Answer 1

Hallo :-)

wie hast du denn die Definitionen zur Landau-Notation kennengelernt?

Comments

Hallo, :)

ich weiß, dass die Landau-Notation benutzt wird, um die Laufzeit bzw. die Anzahl der Schritte in einem Algorithmus zu untersuchen. Dabei versucht man einfachere Vergleichsfunktionen aufzustellen, um die Laufzeit zu klassifizieren.

Wie mache ich das aber am besten in diesem konkreten Fall?

---

Dafür musst du erstmal eine Definition zur Landau-Notation haben. Wie lautet die, die du kennst?

---

Achso meintest du das. Das ist die Definition, die ich kennengelernt habe:

={():∃>0,0>0, so dass für alle ≥0 gilt ≤⋅()}

(wobei ,:ℕ→ℝ+)

---

Ich glaube du meinst diese hier:

$$\mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \ \land f(n)\leq \alpha\cdot g(n) }  \} $$

={():∃>0,0>0, so dass für alle ≥0 gilt ≤⋅()}

Das ergibt überhaupt keinen Sinn!

---

Sorry, mein Fehler, wurde falsch formatiert hier^^

So ist es richtig:

O(f(n)) ={g(n):∃ c>0,n0>0, so dass für alle n ≥ n0 gilt g(n) ≤ c • f(n)}

(wobei ,:ℕ→ℝ+)

---

Ah ok. Das hat mich ziemlich gewundert. ^^

Und was bereitet dir Schwierigkeiten?

---

Mir fehlt ein bisschen der Ansatz. Muss ich zeigen, dass:

∃c´ > 0, ∀n ≥n´0: (2n^2)^2 ≤ c´• 4^n ?

---

1.) Schreibe dir die Funktion doch erstmal vereinfacht hin. Sonst wirds unnötig kompliziert.

2.) Du musst deine Aussage in die Definition einsetzen und dann schauen, was zu zeigen ist:

\(\underbrace{\exists c>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ 4n^4= f(n) \leq c \cdot g(n)=c\cdot 4^n}_{\text{Das willst du zeigen.}} \).

Du musst also eine Konstante \(c>0\) und eine Stelle \(\exists n_0 \in \mathbb{N}\) finden, sodass für alle \( n\geq n_0\) die Ungleichung \(4n^4 \leq c \cdot 4^n\) gilt.