O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hi alle zusammen,
also hier mal meine Aufgabe:
Finden Sie eine Anordnung der folgenden Funktionen, sodass gilt [mm] \forall i:f_i \in O(f_{i+1}):
[/mm]
1. [mm] n^2
[/mm]
2. [mm] (4/3)^n
[/mm]
3. [mm] n2^{\wurzel{\log_{2}n}}
[/mm]
4. n log n
Ich wäre euch sehr dankbar wenn Ihr mir für nachfolgende Beweise sagen könnt, ob Ihr das so in Ordnung und nachvollziehbar findet.
Also meine Anordnung ist
n log n, [mm] n2^{\wurzel{\log_{2}n}}, n^2, (4/3)^n
[/mm]
Beweise:
1) n log n [mm] \in O(n2^{\wurzel{\log_{2}n}})
[/mm]
[mm] n2^{\wurzel{\log_{2}n}} \ge [/mm] n log(n) |:n
[mm] 2^{\wurzel{\log_{2}n}} \ge [/mm] log(n) |log()
[mm] \wurzel{\log_{2}n} [/mm] log(2) [mm] \ge [/mm] log(log(n)) |:log(2)
[mm] \wurzel{\log_{2}n} \ge \frac{log(log(n))}{log(2)} |()^2
[/mm]
[mm] \log_{2}n \ge [/mm] ( [mm] \frac{log(log(n))}{log(2)})^2
[/mm]
und da allgemein [mm] \frac{log(n)}{log(2)} [/mm] = [mm] \log_{2}n [/mm] gilt:
[mm] \log_{2}n \ge (\log_{2}(log(n)))^2
[/mm]
Das ist der einzigste Beweis wo ich mir nicht so sicher bin, ob er durchgeht.
Hier die anderen
2) [mm] n2^{\wurzel{\log_{2}n}} \in O(n^2)
[/mm]
[mm] n2^{\wurzel{\log_{2}n}} \le n^2 [/mm] |:n
[mm] 2^{\wurzel{\log_{2}n}} \le [/mm] n |lg()
[mm] \wurzel{\log_{2}n} [/mm] log(2) [mm] \le [/mm] lg(n) |:log(2)
[mm] \wurzel{\log_{2}n} \le \frac{log(n)}{log(2)}
[/mm]
[mm] \wurzel{\log_{2}n} \le \log_{2}n
[/mm]
[mm] 3)n^2 \in O((\frac{4}{3})^n)
[/mm]
Ich wende l'Hopital an, da [mm] \limes_{n\rightarrow\infty} n^2 [/mm] = [mm] \limes_{n\rightarrow\infty} (\frac{4}{3})^n \rightarrow \infty
[/mm]
Es gilt:
[mm] \limes_{n\rightarrow\infty} \frac{(\frac{4}{3})^n}{n^2} [/mm] =l'Hopital [mm] \limes_{n\rightarrow\infty} \frac{n (\frac{4}{3})^{n-1}}{2n} [/mm] =
[mm] \limes_{n\rightarrow\infty} \frac{(\frac{4}{3})^{n-1}}{2} [/mm] = c < [mm] \infty
[/mm]
Somit gilt [mm] n^2 \in O((\frac{4}{3})^n)
[/mm]
Wäre schön wenn mir jemand sagen könnte, ob etwas daran falsch ist und wie man es besser beweisen könnte.
MfG Andi
|
|
| |
|
Hi Andi,
Also ich würde den ersten Beweis auch so machen, würde aber den letzten Umformungsschritt (das Quadrieren) nicht mehr machen.
Der zweite Beweis stimmt wohl auch.
> [mm]3)n^2 \in O((\frac{4}{3})^n)[/mm]
> Ich wende l'Hopital an, da
> [mm]\limes_{n\rightarrow\infty} n^2[/mm] =
> [mm]\limes_{n\rightarrow\infty} (\frac{4}{3})^n \rightarrow \infty[/mm]
>
> Es gilt:
>
> [mm]\limes_{n\rightarrow\infty} \frac{(\frac{4}{3})^n}{n^2}[/mm]
> =l'Hopital [mm]\limes_{n\rightarrow\infty} \frac{n (\frac{4}{3})^{n-1}}{2n}[/mm]
Hmm, aber es gilt doch [mm] $\left[a^x\right]' [/mm] = [mm] \log \left(a\right) a^x$. [/mm] Dann hast Du aber im Zähler einen Fehler beim Ableiten gemacht, was das Endergebnis aber nicht beeinflußt  :
[m]\mathop {\lim }\limits_{n \to \infty } \frac{{\left( {\frac{4}
{3}} \right)^n }}
{{n^2 }}\mathop = \limits^{{\text{l'Hospital}}} \mathop {\lim }\limits_{n \to \infty } \frac{{\log \left( {\frac{4}
{3}} \right)\left( {\frac{4}
{3}} \right)^n }}
{{2n}}\mathop = \limits^{{\text{l'Hospital}}} \log \left( {\frac{4}
{3}} \right)\mathop {\lim }\limits_{n \to \infty } \frac{{\log \left( {\frac{4}
{3}} \right)\left( {\frac{4}
{3}} \right)^n }}
{2} = \infty[/m]
Grüße
Karl
|
|
|
|
