O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:41 Di 16.10.2007 | | Autor: | tommy987 |
| Aufgabe | | Es ist zu beweisen ob n! < [mm] O(n^n) [/mm] ist. |
Jetzt ist meine Frage, ob es eurer Meinung nach reichen würde für c und n einen Wert anzunehmen und es somit zu beweisen, oder ob man einen anderern Ansatz benötigt...?
Bzw. was könnte es noch für einen Ansatz geben?
lg Tommy
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:56 Di 16.10.2007 | | Autor: | Loddar |
Hallo Tommy!
Betrachte doch entweder den Grenzwert von [mm] $\bruch{f(n)}{g(n)} [/mm] \ = \ [mm] \bruch{n!}{n^n}$ [/mm] und zeige, dass dieser Term für [mm] $n\rightarrow\infty$ [/mm] gegen $0 \ < \ c$ läuft.
Oder verwende folgende ![[]](/images/popup.gif) AbschätzungEingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
:
$$n! \ \approx \ \wurzel{2*\pi*n}*\left(\bruch{\bruch{n}{e}\right)^n \ = \ \bruch{\wurzel{2*\pi*n}}{e^n}*n^n$$
Gruß
Loddar
|
|
|
|
