O-Notation passenden b suchen

27.12.2015, 17:31

Adramelec

O-Notation passenden b suchen

Hallo,

in einer O-Notation Aufgabe würde ich gern um eine Überprüfung bitten, ob ich das richtig gemacht habe: (wobei ich mir bei diesem Log(n) etwas unsicher bin ob man das wirklich so machen kann oder ob ich da nicht "zu groß" geworden bin .. :/ )

[attach]40217[/attach]

Danke!

30.12.2015, 19:04

Adramelec

Auf diesen Beitrag antworten »

push

30.12.2015, 19:24

echnaton

Auf diesen Beitrag antworten »

Aus welcher Menge soll $\begin{eqnarray*} b \end{eqnarray*}$ sein?

Es ist $\begin{eqnarray*} \log^k(n) = \mathcal O(n^\varepsilon) \end{eqnarray*}$ für alle $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} \varepsilon > 0 \end{eqnarray*}$ . Die Abschätzung $\begin{eqnarray*} 1000 \cdot \sin(n) = \mathcal O(1) \end{eqnarray*}$ ist korrekt und $\begin{eqnarray*} \sqrt{n} = \mathcal O(n^\frac{1}{2}) \end{eqnarray*}$ sowieso.

30.12.2015, 19:51

Adramelec

Auf diesen Beitrag antworten »

Ahja, die Menge für b sind die natürlichen Zahlen smile

30.12.2015, 20:08

echnaton

Auf diesen Beitrag antworten »

Ok, hast du dann mit meinem Hinweis die Lösung? Viel kleiner kann $\begin{eqnarray*} b \end{eqnarray*}$ eh nicht werden. Augenzwinkern

30.12.2015, 20:27

Adramelec

Auf diesen Beitrag antworten »

Dann ist b wohl 1. Aber verstehen tue ich es nicht ganz unglücklich

Ist es weil log(n) = O(log(n)). Auch (log(n))^2 = O(log(n)) und somit wäre das Ergebnis eigentlich O(log(n)) - aber da b aus den natürlichen Zahlen kommen muss, nehme ich das höchst größere und das ist 1?

Danke!

30.12.2015, 20:59

echnaton

Auf diesen Beitrag antworten »

Es stimmt, 1 ist das minimalste natürliche $\begin{eqnarray*} b \end{eqnarray*}$ , aber deine Begründung ist falsch.

Für alle reelle $\begin{eqnarray*} b \ge \frac{1}{2} \end{eqnarray*}$ gilt $\begin{eqnarray*} \log^2(n) + 1000 \cdot \sin(n) \cdot \sqrt{n} = \mathcal O(n^b) \end{eqnarray*}$ .
Die Begründung für den zweiten Summanden hast du selbst gegeben. Für den ersten schau dir nochmal meinen ersten Beitrag an.

Zitat:

Es ist $\begin{eqnarray*} \log^k(n) = \mathcal O(n^\varepsilon) \end{eqnarray*}$ für alle $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} \varepsilon > 0 \end{eqnarray*}$ .

30.12.2015, 21:08

Adramelec

Auf diesen Beitrag antworten »

Hi,

ich bin mir nicht sicher ob ich dich richtig verstehe, aber bedeutet, das egal wie hoch die Potenz von log(n) ist, die O-Notation ist immer O(1)

Also als Beispiel: $\begin{eqnarray*} (log(n))^{99} = O(n) \end{eqnarray*}$ ?

30.12.2015, 21:21

echnaton

Auf diesen Beitrag antworten »

Zitat:

Original von Adramelec
egal wie hoch die Potenz von log(n) ist, die O-Notation ist immer O(1)

Nein, $\begin{eqnarray*} \mathcal O(1) \end{eqnarray*}$ habe ich in diesem Zusammenhang nie behauptet.

Zitat:

Also als Beispiel: $\begin{eqnarray*} (log(n))^{99} = O(n) \end{eqnarray*}$

Das stimmt, oder auch $\begin{eqnarray*} (\log(n))^{99} = \mathcal O(n^{0,1}) \end{eqnarray*}$ oder $\begin{eqnarray*} (\log(n))^{10000} = \mathcal O(n^{0,00000123}) \end{eqnarray*}$ .

Allgemein halt
$\begin{eqnarray*} \log^k(n) = \mathcal O(n^\varepsilon) \end{eqnarray*}$ für alle $\begin{eqnarray*} k \in \mathbb N \end{eqnarray*}$ und $\begin{eqnarray*} \varepsilon > 0 \end{eqnarray*}$ . Wink

30.12.2015, 21:25

Adramelec

Auf diesen Beitrag antworten »

Danke. Und ja das O(1) war ein Tippfehler, ich wollte O(n) schreiben.. ;-)

Danke nochmal!

Neue Frage »

Antworten »

O-Notation passenden b suchen

Verwandte Themen