Czy log (n!) = Θ (n · log (n))?

Mam pokazać, że log ( n !) = Θ ( n · log ( n )) .

Podano podpowiedź, że powinnam pokazać górną granicę za pomocą n ^n, a dolną granicę za pomocą ( n / 2) ^{( n / 2)} . Nie wydaje mi się to aż tak intuicyjne. Dlaczego miałoby tak być? Z pewnością widzę, jak przekonwertować n ⁿ na n · log ( n ) (tj. Zalogować obie strony równania), ale to trochę działa wstecz.

Jakie byłoby właściwe podejście do rozwiązania tego problemu? Czy powinienem narysować drzewo rekurencyjne? Nie ma w tym nic rekurencyjnego, więc nie wydaje się to prawdopodobne.

Zapamietaj to

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

Możesz uzyskać górną granicę

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

Możesz uzyskać dolną granicę, robiąc podobne rzeczy po wyrzuceniu pierwszej połowy sumy:

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2) 

Zdaję sobie sprawę, że jest to bardzo stare pytanie z zaakceptowaną odpowiedzią, ale żadna z tych odpowiedzi nie korzysta z podejścia sugerowanego przez wskazówkę.

To dość prosty argument:

n!(= 1 * 2 * 3 * ... * n) jest iloczynem nliczb mniejszych lub równych n. Dlatego jest mniejszy niż iloczyn nliczb wszystkich równych n; tj n^n.

Połowa liczb - tj. n/2Ich - w n!produkcie jest większa lub równa n/2. Dlatego ich iloczyn jest większy niż iloczyn n/2liczb wszystkich równych n/2; tj (n/2)^(n/2).

Weź dzienniki, aby ustalić wynik.

Przepraszam, nie wiem, jak używać składni LaTeX na stackoverflow ..

Zobacz przybliżenie Stirlinga :

ln (n!) = n * ln (n) - n + O (ln (n))

gdzie ostatnie 2 terminy są mniej znaczące niż pierwszy.

Dla dolnej granicy,

lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
       >= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
       = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
       = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
       = n/2 lg n - 1/2

lg (n!)> = (1/2) (n lg n - 1)

Łączenie obu granic:

1/2 (n lg n - 1) <= lg (n!) <= N lg n

Wybierając niższą stałą graniczną większą niż (1/2), możemy skompensować -1 wewnątrz nawiasu.

Zatem lg (n!) = Theta (n lg n)

Pomagając ci dalej, gdzie zostawił cię Mick Sharpe:

Wyprowadzenie jest dość proste: patrz http://en.wikipedia.org/wiki/Logarithm -> Teoria grupy

log (n!) = log (n * (n-1) * (n-2) * ... * 2 * 1) = log (n) + log (n-1) + ... + log (2 ) + log (1)

Pomyśl o n jako nieskończenie dużym . Co to jest nieskończony minus jeden? czy minus dwa? itp.

log (inf) + log (inf) + log (inf) + ... = inf * log (inf)

A potem pomyśl o inf jako n.

Dzięki, znalazłem twoje odpowiedzi przekonujące, ale w moim przypadku, muszę użyć Θ właściwości:

log(n!) = Θ(n·log n) =>  log(n!) = O(n log n) and log(n!) = Ω(n log n)

w celu zweryfikowania problemu znalazłem tę stronę internetową, w której wyjaśniono cały proces: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

To może pomóc:

e ln (x) = x

i

(l m ) n = l m * n

http://en.wikipedia.org/wiki/Stirling%27s_approximation Przybliżenie Stirlinga może ci pomóc. Jest to bardzo pomocne w rozwiązywaniu problemów silnych związanych z ogromnymi liczbami rzędu 10 ^ 10 i więcej.