0 Daumen
1,1k Aufrufe

könnte mir jemand bitte diese aussagen mit n0 und c beweisen bzw. widerlegen?3613232F-9754-4F47-9D47-5754B1C07966.jpeg

Text erkannt:

1. \( \frac{n^{4}}{\log (n+2)} \in \mathcal{O}\left(2 n^{2}\right) \)
2. \( 3 n+2 \log n \in \mathcal{O}(n \cdot \log n) \)
3. \( 42 \cdot n^{2} \in \mathcal{O}\left(2^{\log \left(n^{3}\right)}\right) \)
4. \( 8^{n} \in \mathcal{O}\left(2^{2 n}\right) \)

Avatar von

1 Antwort

0 Daumen

Hallo :-)

Die formale Definition für die Groß O-Notation lautet in etwa:Es sei \(g: \mathbb{N}\rightarrow \mathbb{R}\). Dann ist$$ \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) }  \}. $$

Analog lässt sich schreiben:

$$ \Omega(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \beta>0 \ \exists n_1 \in \mathbb{N} \ \forall n\geq n_1:\ \underbrace{g(n) \geq \beta \cdot f(n)\geq 0}_{g(n) \geq \beta\cdot f(n) \ \land \beta \cdot f(n)\geq 0 }  \}. $$


Damit rechne ich dir mal zwei (je eins wahr und das andere falsch) von den vier Behauptungen vor:

Eins vorab. Ich behandle hier den Logarithmus beispielhaft als den binären Logarithmus, aber das Prinzip bleibt dasselbe.

Zu 2.). Diese Behauptung ist wahr. Das kann man durch folgende Abschätzungskette einsehen:

\( \begin{aligned}0&\stackrel{n\geq 1}{\leq} 3 \cdot n+2\cdot \log(n)\\[15pt]&\stackrel{n\geq 2}{\leq} 3 \cdot n\cdot \log(n)+2\cdot \log(n)\\[15pt]&\stackrel{n\geq 2}{\leq} 3 \cdot n\cdot \log(n)+2\cdot \log(n)\cdot n\\[15pt]&=5\cdot n \cdot \log(n) \end{aligned}\)

Also gilt mit \(n_0=2\) und \(\alpha=5\) die Eigenschaft

\( 3 n+2 \log n \in \mathcal{O}(n \cdot \log n) \).


Zu 1.). Diese Behauptung ist falsch. Sicher kennst du diese Beziehung:

\(f\in \mathcal{O}(g) \Leftrightarrow g\in \Omega(f)\), die man aber sehr schnell mit der Definition zeigen kann: (kurz)

\(f\in \mathcal{O}(g) \Leftrightarrow 0\leq f(n) \leq \alpha \cdot g(n) \stackrel{\alpha>0}{\Leftrightarrow} 0\leq \underbrace{\frac{1}{\alpha}}_{=:\beta} \cdot f(n) \leq g(n) \Leftrightarrow g\in \Omega(f)\).

Also gilt ja auch dadurch \(f\notin \mathcal{O}(g) \Leftrightarrow g\notin \Omega(f)\).

Damit zeige ich also, dass \(\underbrace{2\cdot n^2}_{=:g(n)} \notin \Omega\left(\underbrace{\frac{n^4}{\log(n+2)}}_{=:f(n)}\right)\).

Dafür negiert man die Omega-Definition:

\(g\notin \Omega(f) \Leftrightarrow \quad \forall \beta>0\ \forall n_1\in \mathbb{N}\ \exists n\geq n_1: \ \underbrace{g(n) < \beta\cdot f(n)}_{(1)} \ \lor \underbrace{\beta \cdot f(n) < 0}_{(2)}   \)


Teil (2) ist beim Betrachten immer falsch, sodass (1) gezeigt werden muss, damit diese Oder-Aussage wahr ist. Jetzt ist Basteln angesagt. Es soll also in Abhängigkeit von \(\beta\) und \(n_1\) ein \(n\geq n_1\) gefunden werden, sodass

\(2\cdot n^2=g(n) < \beta\cdot f(n)=\beta\cdot \frac{n^4}{\log(n+2)}\)

gilt. Jetzt probiert man halt so paar Sachen aus:

Statt \(2\cdot n^2 < \beta\cdot \frac{n^4}{\log(n+2)}\)

betrachte ich mal zb

\(2< \beta\cdot \frac{n^2}{\log(n+2)}\)

und damit betrachte ich

\(2< \beta\cdot n\)

und damit \(\frac{2}{\beta}<n\). Mit \(\frac{2}{\beta}<n\) könnte man arbeiten. Ich fordere also, dass \(\frac{2}{\beta}<n\) gilt. Dann habe ich

\(\frac{2}{\beta}<n \stackrel{n\leq 2}{\leq} n\cdot \underbrace{\frac{n}{\log(n+2)}}_{\geq 1}\).

Jetzt muss noch \(n_1\) ins Spiel kommen.

Dafür fordere ich nun als Ergebnis \(n>\max\left(n_1,2,\frac{2}{\beta}\right)\).

Damit hat man also

\(\begin{aligned}&\frac{2}{\beta}<n\leq n\cdot \frac{n}{\log(n+2)}=\frac{n^2}{\log(n+2)} \\&\Leftrightarrow \frac{2}{\beta}\cdot n^2 < \frac{n^4}{\log(n+2)} \\&\Leftrightarrow 2\cdot n^2 <\beta\cdot \frac{n^4}{\log(n+2)}\end{aligned}\)

Und genau das wahr zu zeigen.

Avatar von 14 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community