O-Notation-Beweis < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:39 Di 23.10.2007 | | Autor: | Dani7 |
| Aufgabe | Die kleine o-Notation ist wie folgt definiert: f(n)= o(g(n)) wenn gilt lim f(n) /g(n)=0 (wenn n gegen unendlich).
Zeigen Sie, dass [mm] n^a= o(c^n) [/mm] für alle a> 0 und c>1. |
Ich habe versucht, diese aufgabe mit Hilfe der Regel von L'Hospital zu lösen, aber diese scheint hier nicht zu einer Lösung zu führen.
Wenn ich nämlich Zähler und Nenner jeweils ableite sieht das folgendermaßen aus:
lim ( [mm] n^a/ c^n) [/mm] = lim ( [mm] a*n^{a-1}/(c^n*lnc) [/mm] = a/lnc *lim (n^(a-1) / [mm] c^n).
[/mm]
Bei der Ableitung wird also immer nur im Zähler der Exponent um Eins reduziert und ist daher immer gleichwertig mit der ursprünglichen Angabe.
vielleicht könnte mir jemand einen Hinweis geben, wie man hier zur Lösung kommt?
Danke
|
|
| |
|
Hallo Dani7,
> Die kleine o-Notation ist wie folgt definiert: f(n)=
> o(g(n)) wenn gilt lim f(n) /g(n)=0 (wenn n gegen
> unendlich).
> Zeigen Sie, dass [mm]n^a= o(c^n)[/mm] für alle a> 0 und c>1.
> Ich habe versucht, diese aufgabe mit Hilfe der Regel von
> L'Hospital zu lösen, aber diese scheint hier nicht zu einer
> Lösung zu führen.
> Wenn ich nämlich Zähler und Nenner jeweils ableite sieht
> das folgendermaßen aus:
>
> lim ( [mm]n^a/ c^n)[/mm] = lim ( [mm]a*n^{a-1}/(c^n*lnc)[/mm] = a/lnc *lim
> (n^(a-1) / [mm]c^n).[/mm]
>
> Bei der Ableitung wird also immer nur im Zähler der
> Exponent um Eins reduziert und ist daher immer gleichwertig
> mit der ursprünglichen Angabe.
Ich denke, dein Ansatz ist trotzdem richtig. Alles, was du tun mußt,
ist diesen Ableiteprozess solange L'Hospital gilt, fortzusetzen:
[mm]\lim_{n\to\infty}{\frac{n^a}{c^n}} = \lim_{n\to\infty}{\frac{an^{a-1}}{c^n\ln c}}=\frac{a}{\ln c}\cdot{\lim_{n\to\infty}{\frac{n^{a-1}}{c^n}}}=\frac{a}{\ln c}\cdot{\frac{a-1}{\ln c}\cdot{\lim_{n\to\infty}{\frac{n^{a-2}}{c^n}}}}[/mm]
[mm]=\dotsm =\frac{a!}{\ln^a c}\cdot{\lim_{n\to\infty}{\frac{n^{a-a}}{c^n}}}[/mm]
Oder anders ausgedrückt: Alles, was einen Anfang hat,
hat auch ein Ende, Neo! ![[happy]](/images/smileys/happy.gif "[happy]") ![[bonk]](/images/smileys/bonk.gif "[bonk]")
Grüße
Karl
|
|
|
|
