0 Daumen
1,2k Aufrufe


Für die Aufgabenteile e) & f \mathrm{f} ) betrachten wir Logarithmen als Funktionen von N \mathbb{N} nach R \mathbb{R} . Weiter seien a,bR>0\{1} a, b \in \mathbb{R}_{>0} \backslash\{1\} und a>b. a>b . Sie dürfen, falls nötig, die üblichen Rechenregeln für Logarithmen verwenden. Zeigen oder widerlegen Sie:


(a) n2+2n+1=O(n2) n^{2}+2 n+1=O\left(n^{2}\right)

(b) (n+1)3=O(n3) (n+1)^{3}=O\left(n^{3}\right)

(c) 2n=O(n!) 2^{n}=O(n !)

(d) loga(n)=O(logb(n)) \log _{a}(n)=O\left(\log _{b}(n)\right)


(e) logb(n)=O(loga(n)) \log _{b}(n)=O\left(\log _{a}(n)\right)


Also ich habe bei

a) n2+2n+1n2 \frac{ n^2+2n+1}{n^2} n2n2 \frac{n^2}{n^2} 2nn2 \frac{2n}{n^2} 1n2 \frac{1}{n^2} ≤ 1 + 2 + 1 ≤ 10 (irgendeine Zahl)


Bei

b) (n + 1)3 = n3 +3n2 +3n +1 = O(n3)

n3+3n2+3n+1n3 \frac{ n^3+3n^2 +3n +1}{n^3} = n3n3 \frac{n^3}{n^3} + 3n2n3 \frac{3n^2}{n^3} 3nn3 \frac{3n}{n^3}  +  1n3 \frac{1}{n^3} ≤ 1 + 3 + 3 + 1 ≤ 10 (irgendeine Zahl)


Bei c)

(22)n2( \frac{2}{2})^\frac{n}{2} * 222 \frac{2}{2}   =  (222)n2( \frac{2}{2}^2)^\frac{n}{2}  2n/2n \frac{2}{n/2}^n (also falsch)


Ist das korrekt und weiß jemand, wie man d) und e) zeigen oder widerlegen soll?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Hallo:-)

Deine Rechenwege sind keine Beweise. (a), (b) , (c) und (e) sind wahr. (d) ist falsch.

Ich schreibe mal die ,,übliche" Landau-Definition für groß-O hin:

O(g) : ={f :  NR :  α>0 n0N nn0 :  0f(n)αg(n)0f(n) f(n)αg(n)} \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) } \}

Du musst also eine Konstante α>0\alpha>0 und eine Stelle n0Nn_0 \in \mathbb{N} finden, sodass für alle nn0 n\geq n_0 die Ungleichung 0f(n)αg(n)0\leq f(n)\leq \alpha\cdot g(n) gilt.


Nebenbei bemerkt ist die Schreibweise f=O(g)f=\mathcal{O}(g) absolut falsch. O(g)\mathcal{O}(g) ist eine Menge! Sie beschreibt doch, die Menge aller Funktionen f :  NRf:\ \mathbb{N}\rightarrow \mathbb{R}, die bis auf eine Konstante höchstens so schnell wie gg wachsen. Die Schreibweise fO(g)f\in \mathcal{O}(g) ist von daher korrekt.


Ich führe mal den Beweis für die Definition bei (a) vor:

Es ist n2+2n+1O(n2)n^2+2n+1\in \mathcal{O}(n^2) zu zeigen. Dabei ist f(n)=n2+2n+1f(n)=n^2+2n+1 und g(n)=n2g(n)=n^2.

Ich suche also eine Konstante α>0\alpha>0 und eine Stelle n0Nn_0 \in \mathbb{N}, sodass für alle nn0 n\geq n_0 die Ungleichung 0n2+2n+1=f(n)αn2=g(n)0\leq \underbrace{n^2+2n+1}_{=f(n)}\leq \alpha\cdot \underbrace{n^2}_{=g(n)} gilt.

Entweder man sieht bereits, welche Konstante α>0\alpha>0 und Stelle n0Nn_0\in \mathbb{N} zu verwenden sind, denn dann kannst du mit Induktion die Ungleichung zeigen. Oder man bekommt diese durch geschicktes Abschätzen mitgeliefert. Ich wähle letzteres:

n2+2n+1n2n2+n2+1n2n2+n2+n2=3n2 \begin{aligned}&n^2+2n+1\\\stackrel{n\geq 2}{\leq} &n^2+n^2+1\stackrel{n\geq 2}{\leq} &n^2+n^2+n^2=3\cdot n^2\end{aligned}

Also wähle ich α=3\alpha=3 und n0=2n_0=2. Damit ist n2+2n+1O(n2)n^2+2n+1\in \mathcal{O}(n^2).

Avatar von 15 k

Wow danke. Kannst du vielleicht noch die Beweise von b) und c) kurz zeigen? Die anderen habe ich schon

b) kannst du analog wie a) machen und c) zeige durch Induktion die Ungleichung 2nn!2^n\leq n! für alle nN4n\in \mathbb{N}_{\geq 4}.

Also bei b) auch dieselben Werte für die Konstante und n?

Nein. Du sollst durch Abschätzen auf die Werte für n und α kommen.

Bei b) Könnte ich für die Konstante den Wert 25 geben und für n = 3 dann wäre das richtig beispielsweise

Ja, das geht auch. Das kannst du durch Induktion zeigen oder du zeigst es durch geschicktes Abschätzen.

Ah, ich hab's. Für die Konstante 3 und für n=1

Okay, ich würde aber lieber die 3 und die 1 benutzen

Was ist 3 und was ist 1?

Konstante = 3 und n = 1

Das funktioniert nicht. Wenn dann n=3, wenn du α=3 wählst. Aber nun musst du die entsprechende Ungleichung beweisen.

Sprechen wir von derselben Aufgabe b) mit n3? Stimmt, du hast Recht

Genau. Mache einfach eine Induktion.

aber im letzten Schritt wäre n3 + n3 +n3 + n3 Ungleich 3 * n3

Was rechnest du überhaupt gerade?

alles gut, danke für die Hilfe

Ein anderes Problem?

Stell deine Frage