Komplexität |
| 17.01.2018, 06:52 | Auf diesen Beitrag antworten » |
| Henning | 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 
|
|
|
|
| 18.01.2018, 15:00 | Auf diesen Beitrag antworten » |
| as_string | 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 |
|
|
