---

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