Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexität » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Komplexität
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Henning
unregistriert
Komplexität Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Kann mir hier jemand sagen, warum

n^n schneller wächst als n^2 * n! ?

Vermutlich kann man das mit der Stirlingschen Näherung zeigen, aber ich komme leider nicht drauf

Vielen lieben Dank smile
17.01.2018 06:52
as_string as_string ist männlich
Haudegen


Dabei seit: 06.11.2013
Beiträge: 639
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Naja, nach der Stirling-Formel hast Du ja einen Vorfaktor, indem Wurzel-n vorkommt, und dann noch n^n durch e^n. Das bedeutet, man muss zeigen, dass n^(2,5) langsamer wächst als e^n, richtig? Da ein Ausdruck mit n im Exponenten immer schneller wächst als eine Potenz von n ist das aber ziemlich offensichtlich.
Ersetze doch einfach mal das n! in n^2*n! durch den Stirling-Ausdruck und fasse das zusammen. Dann kannst Du n^n ja auf beiden Seiten weg "kürzen".

Gruß
Marco
18.01.2018 15:00 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexität