O-Notation-Beweis < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:38 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*ln) [/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
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:42 Di 23.10.2007 | | Autor: | rainerS |
Hallo!
Schreibe [mm]\bruch{n^a}{c^n} = \bruch{\mathrm{e}^{a\ln n}}{\mathrm{e}^{n\ln c}} = \mathrm{e}^{a\ln n-n\ln c}[/mm].
Viele Grüße
Rainer
|
|
|
|
