O-Notation beweisen von Behauptung

27.12.2015, 18:25

Adramelec

O-Notation beweisen von Behauptung

Hallo,
ich habe hier 3 Behauptungen und würde gern wissen ob ich das richtig gemacht habe.

1. Beispiel: [attach]40214[/attach]
2. Beispiel: [attach]40215[/attach]
3. Beispiel: [attach]40216[/attach]

Danke!

30.12.2015, 20:05

Adramelec

Auf diesen Beitrag antworten »

push

30.12.2015, 23:52

echnaton

Auf diesen Beitrag antworten »

a)
Die Teilaufgabe ist falsch. Wende bei $\begin{eqnarray*} \log(n^2) \end{eqnarray*}$ das Logarithmusgesetz an und gib eine allgemeine Formel $\begin{eqnarray*} \log(n^k) = \mathcal O(f) \end{eqnarray*}$ an, wobei $\begin{eqnarray*} f \end{eqnarray*}$ möglichst minimal ist.

Verwende im zweiten Summanden $\begin{eqnarray*} \log(n) = \mathcal O(\sqrt{n}) \end{eqnarray*}$ . Kennst du die Inklusionskette häufig verwendeter Funktionen? de.wikipedia.org/wiki/Landau-Symbole#Beispiele_und_Notation

b)
Deine Lösung ist richtig. Ist dir klar, warum $\begin{eqnarray*} \mathcal O(2^n) \end{eqnarray*}$ und $\begin{eqnarray*} \mathcal O(2^{2n}) \end{eqnarray*}$ zwei verschiedene Klassen sind?

c)
Ist richtig, wobei sich das "gegen 0" nur auf den Grenzwert $\begin{eqnarray*} \lim_{n \to \infty} 3^{-n} \end{eqnarray*}$ bezieht, nicht jedoch auf die Menge* $\begin{eqnarray*} \mathcal O(3^{-n}) \end{eqnarray*}$ .

* Weil es sich um Menge handelt, ist die Schreibweise $\begin{eqnarray*} f = \mathcal O(g) \end{eqnarray*}$ mitunter problematisch, aber üblich.

31.12.2015, 00:02

echnaton

Auf diesen Beitrag antworten »

Ich sehe gerade b) und c) sind vertauscht. Nun ja..

31.12.2015, 00:47

Adramelec

Auf diesen Beitrag antworten »

Hallo,

danke für deine Antworten.
Ja das mit b und c vertauscht ist .. naja.

b) naja weil ja der exponent nochmal größer ist wie wenn $\begin{eqnarray*} 2^{1n} \end{eqnarray*}$ stehen würde (bzw. in diesem Fall ja auch tut)?

c) Ok smile

Ich glaube auch in meinem Skriptum gelesen zu haben, dass die Schreibweise mathematisch nicht 100% korrekt ist, aber sich so eingebürgert hat.. und wir eigentlich nur so damit arbeiten smile

a) und zu a einen neuen screenshot .. smile

Ich hoffe ich hab deine Hinweise richtig umgesetzt Gott

[attach]40241[/attach]

31.12.2015, 11:05

echnaton

Auf diesen Beitrag antworten »

Zitat:

und zu a einen neuen screenshot .. Ich hoffe ich hab deine Hinweise richtig umgesetzt

Ich dachte eigentlich an $\begin{eqnarray*} \log(n^2) = 2 \log(n) = \mathcal O(\log) \end{eqnarray*}$ . Das kannst du wiederum mit $\begin{eqnarray*} k \end{eqnarray*}$ im Exponenten verallgemeinern, aber $\begin{eqnarray*} \mathcal O(\sqrt{n}) \end{eqnarray*}$ geht hier auch. Hauptsache nicht über $\begin{eqnarray*} \mathcal O(n) \end{eqnarray*}$ .

Zitat:

b) naja weil ja der exponent nochmal größer ist wie wenn $\begin{eqnarray*} 2^{1n} \end{eqnarray*}$ stehen würde (bzw. in diesem Fall ja auch tut)?

Es ist bekanntlich eine gute Merkhilfe, dass "konstante Faktoren bei der $\begin{eqnarray*} \mathcal O \end{eqnarray*}$ -Notation nicht beachtet werden müssen". Warum kann ich die Konstante 2 hier im Exponenten nicht vernachlässigen? Versuch das mal über die Definition des Landau-Symbols.

31.12.2015, 13:46

Adramelec

Auf diesen Beitrag antworten »

danke

@b) Weil die Konstante 2 ja im Exponenten steht? So wie bei x^{2} ich auch nicht die 2 weglassen kann, obwohl es eine Konstante ist?

31.12.2015, 15:02

echnaton

Auf diesen Beitrag antworten »

Im Prinzip ja. Besonders deutlich wird es, wenn man das zu $\begin{eqnarray*} (2^n)^2 \end{eqnarray*}$ umformt. Mir würde das aber nicht ausreichen. Kannst du $\begin{eqnarray*} 2^{2n} \not\in \mathcal O(2^n) \end{eqnarray*}$ auch über die Definition zeigen?

Neue Frage »

Antworten »

O-Notation beweisen von Behauptung

Verwandte Themen