| Autor |
Beitrag |
    
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 53
Registriert: 03-2001
| | Veröffentlicht am Montag, den 18. November, 2002 - 17:46: | 
|
hi.
in informatik sollten wir als übungsaufgabe verschiedene funktionen danach sortieren, wie schnell sie mit n wachsen. bei der besprechung meinte unser übungsleiter, daß c^(c^n) (c>1, konstant) schneller wächst als n^n. das widerspricht irgendwie meiner vorstellung. auf nachfragen konnte er als 'beweis' nur die graphen der funktionen vorlegen, auf denen es zumindest so aussah, als ob c^(c^n) schneller wächst.
frage: wie beweist (oder widerlegt?) man mathematisch, daß n^n < c^(c^n) für n->oo ?
danke
markus |
heimdall (gjallar)
Neues Mitglied
Benutzername: gjallar
Nummer des Beitrags: 3
Registriert: 11-2002
| | Veröffentlicht am Montag, den 18. November, 2002 - 18:38: |
|
Es gilt sogar die symmetrische Form
n^(n^c) < c^(c^n)
Beide Seiten der Ungleichung logarithmieren, dann das Standardargument: eine Potenzfunktion (li. Seite n^c * ln(n) < n^(c+1)) wächst langsamer als eine Exponentialfunktion mit Basis > 1 (re. Seite ln(c) * c^n ).
Gruß,
Gjallar
|
Orion (orion)
Erfahrenes Mitglied
Benutzername: orion
Nummer des Beitrags: 371
Registriert: 11-2001
| | Veröffentlicht am Mittwoch, den 20. November, 2002 - 08:55: |
|
Hallo,
Die Aussage "nn wächst langsamer als
ccn " besagt etwas mehr als nur
die < - Beziehung, nämlich
limn®oo(nn*c-cn) = 0
Dazu betrachten wir (wie heimdall) den
Logarithmus des fraglichen Quotienten,
also
cn*[ (n log n)/cn - log c ]
Weil (n log n)/cn ® 0 für n ® oo
strebt der [ ]-Ausdruck gegen - log c < 0,
daher der ganze Ausdruck gegen - oo.
mfG Orion
|
|
