O-Notation-Beweis < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:29 Di 16.10.2007 | | Autor: | Dani7 |
| Aufgabe | | Beweisen oder wiederlegen Sie, dass n! = [mm] O(n^n). [/mm] |
Ich wollte diese Fragestellung mit dem Grenzwert berechnen, der besagt, dass n! der Kompexitätsklasse [mm] n^n [/mm] angehört, wenn f(n)/g(n) kleiner als Unendlich ist, wenn n gegen unendlich geht.
dazu habe ich versucht n! folgendermaßen zu zerlegen:
n! = n*(n-1)!
und [mm] n^n [/mm] so zerlegt:
[mm] n^n= [/mm] n*(n^(n-1))
dieser Ansatz führt für mich aber ins nirgendwo, deshalb wollte ich fragen ob es möglich ist, diese Fragestellung mit einer Grenzwertberechnung zu lösen?
Ich habe auch versucht, die Fragestellung weiters so zu beantworten:
Es gilt ja für die O-Notation: f(n) < c*g(n)
a) Fall n= n0=10
c=100
n0=10
wenn man das nun in die Gleichung einsetzt erhält man:
10! = 100 *10^10
damit wäre ja diese Bedingung bewiesen
aber Fall b) läßt sich wieder nicht ausrechnen, da ich nicht weis wie man mit n! umgehen kann
b) Fall n> n0
c=100
n*(n-1)! < 100*n*n^(n-1)
ab hier komm ich nicht weiter, deswegwn wollte ich fragen ob irgendwer so nett wäre und mir sagen könnte ob es überhaupt möglich ist mit n! hier zu rechnen oder ob nur eine logische Schlussfolgerung möglich ist?
Wenn es zu rechnen ginge, wäre es nett mir bitte einen Ansatz zu sagen und wenn nur eine Abschätzung möglich ist, dann wäre es auch nett, wenn mir jemand in dieser Richtung eine Wegweisung geben könnte.
Danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:46 Di 16.10.2007 | | Autor: | Dani7 |
Tut mir leid, ich hab grad gesehn, dass jemand dasselbe Problem hat wie ich, ich danke natürlich auch auf diese Weise für die tolle Hilfe!!
lg daniela
|
|
|
|
