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
|
|