Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Komplexität (http://www.informatikerboard.de/board/thread.php?threadid=3841)
Geschrieben von Henning am 17.01.2018 um 06:52:
Komplexität
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
Geschrieben von as_string am 18.01.2018 um 15:00:
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
Forensoftware: Burning Board, entwickelt von WoltLab GmbH