0 Daumen
533 Aufrufe

Aufgabe:

Kann mir jemand weiterhelfen, ich würde gerne wissen welche Funktion schneller wächst.


f(n) = log(n!)

g(n) = n log n


Problem/Ansatz:

Grundsätzlich weiß ich, dass n log n schneller wachsen würde als log n, da n! aber schneller wächst bin ich mir aber unsicher welche Auswirkungen das in dem oben genannten Zusammenhang hat.

Avatar von

3 Antworten

0 Daumen
 
Beste Antwort

n^n ≥ n!

für n > 1 aber bereits n^n > n!

Also nutzen wir das mal

log(n!) ≤ log(n^n) = n * log(n)

Alles klar soweit?

Avatar von 477 k 🚀

Danke für die Antwort! Hat mir auf jeden Fall weiter geholfen. Was ich mich allerdings noch Frage würde dann log(n!)  Element von O(n) sein ?

Es ist ja mehr als linear aber weniger als quadratisch also ich würde

O(n log n) für den quasi linearen Aufwand als Abschätzung nehmen.

0 Daumen

hallo

log(n!)=\( \sum\limits_{k=0}^{n}{log(k)} \) damit solltest du es leicht haben. Immer an die log Gesetzt denken!

Grenzen der Summe falsch , richtig nach Hinweis von Arsinoe: log(n!)=\( \sum\limits_{k=1}^{n}{log(k)} \)

Gruß lul

Avatar von 106 k 🚀
log(n!)=\( \sum\limits_{k=0}^{n}{log(k)} \) ... Immer an die log Gesetzt denken!

Was ist denn log(0) ?

0 Daumen

Nach Logarithmengesetzen ist f(n) = ln 1 + ln 2 + ln 3 + ... + ln(n).

Das ist die Summe von n verschiedenen Logarithmen.

Bei g(x) hat man n mal den gleichen Logarithmus ln (n), also ln(n) + ln(n) + ... +ln(n).

Da bei g(n) alle Summanden (außer dem letzten) größer sind als die Summanden von f(n) und der letzte Szummand von f(n) auch nicht größer ist als der letzte Summand von g(n), muss g(n) immer größer sein als f(n).

Avatar von 53 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community