Logarithmus der Fakultät?
Moin moin. Unszwar geht es darum, dass man die asymptotische Notation zeigen soll, also das log2 (n!) genau so schnell wächst wie (n log2 n), bei der Fakultätsfunktion n! = n* (n-1) * (n-2)...1.
Hierzu muss in Aufgabenteil a) gezeigt werden, dass log 2 (n!) höchstens so schnell wächst wie (n log2 n) und in Aufgabenteil b), dass es mindestens so schnell wächst
Mein Ansatz. Wenn man zwei Funktionen teilt und das Ergebnis gegen unendlich geht, gilt O (höchstens so schnell). Wenn das Ergebnis gegen 0 geht, gilt Ω. Wenn das Ergebnis der Division ein konstanter Faktor ist, gilt Θ. Man könnte also log 2n! durch (n log 2n) teilen und zeigen, dass ein konstanter Faktor rauskommt und daher Θ gilt.
Die Aufgabe zwingt einen jedoch dazu, sowohl O und dann Ω zu zeigen
Ich müsste also log2n! durch (n log2 n) teilen und zeigen, dass es gegen unendlich geht, um O zu zeigen. Aber dann müsste man auch zeigen, dass es gegen 0 geht. Der Ansatz funktioniert also nicht.
Eine andere Möglichkeit wäre
log2 n! <= c * (n log2 n) zu rechnen. Aber dann müsste man auch log 2 n! >= c * (n log 2n) zeigen. Und leider kann ich n! nicht wegkürzen. :(
3 Antworten
a)
log2(n!) = log2(n) + ... + log2(1)
Man beachte, dass die Logarithmus-Funktion monoton zunimmt. Es gilt daher:
log2(a) > log2(b) für a > b > 0
entsprechend folgt:
log2(n!) <= n*log2(n)
--> log2(n!) geht nicht schneller gegen Unendlich als n*log2(n).
(Alternativ: n! <= n^n --> log(n!) <= log(n^n) = n*log(n) )
b)
Hier kann man ähnlich argumentieren, heißt:
n! >= n^(n/2)
siehe hierfür bspw.: (ganz unten ... )
https://www.mathelounge.de/112546/aufgabe-zu-abschatzungen-von-fakultaten-zeige-n-n-2-n
Es folgt damit (Monotonie):
log2(n!) >= log2(n^(n/2)) = (n/2)*log2(n)
Es folgt damit also:
log2(n!) >= c*log2(n)*n
und damit die zu zeigende Aussage in b).
Wenn du einen allgemeineren Ausdruck beweisen kannst, dann folgen die beiden speziellere Fälle daraus, insofern wäre das eine unanfechtbare Lösung, solange dein angebrachter Beweis tatsächlich stichhaltig sein sollte.
Die kleiner Relation scheint mir übrigens auch recht leicht, wenn man das Produkt in der Fakultät durch Logarithmustrgeln in eine Summe umschreibt.
Ich nehme mal an eine Taylor-Entwicklung ist nicht ohne weiteres gestattet? Eventuell findest du unter dem Begriff "Stirling Formel" etwas brauchbares, die Formel scheint verwandt.
Ich hoffe das hilft zumindest weiter.
Danke. Also mein Ansatz wäre jetzt zu zeigen, dass
log2 n! ≤ c * (n * log2 n )
aber ich weiß nicht, wie ich am geschicktesten umformen soll.
Taylor-Entwicklung hatten wir in "Mathematik für Informatiker Teil 1" mal gehabt. Stirling-Formel sagt mir gar nichts. Laut Google kann man daraus folgen, dass
log2 n! annäherend n log n -n entspricht. Also könnte man sagen
log2 n! ≤ c * (n * log2 n )
?
Habe jetzt das hier als Lösungsvorschlag gefunden, wo das ganze erklärt wird. (Allerdings mit log stat log2, aber sollte ja keinen Unterschied machen)
https://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm
Ich verstehe allerdings einen Schritt nicht, unszwar
"Replacing all remaining terms by the smallest one gives
Warum darf der gute Mann einfach alle Termine duirch n/2 log n/2 ersetzen? Da stand ja vorher
Dann fallen ja Faktoren wie das +1 aus log (n/2 + 1) oder das +2 aus log (n/2 + 2) völlig unter dem Tisch?
