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

Question

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

Podpowiedź podano, że należy pokazują górną granicę z nⁿ i wykazują niższe wiązanie z (n/2) ^(n/2) . Nie wydaje mi się to aż tak intuicyjne. Dlaczego tak się stało? Mogę zdecydowanie zobaczyć, jak konwertować nⁿ do n · log (n) (tj zalogować obie strony równania), ale to rodzaj działa wstecz.

Jakie byłoby właściwe podejście do rozwiązania tego problemu? Czy powinienem narysować drzewo rekursji? Nie ma nic o tym rekurencyjne tak, że nie wydaje się prawdopodobny podejścia ..

Answer 1

Pamiętaj, że

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

Można dostać górny związany

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

I można dostać dolna granica, wykonując podobną czynność po odrzuceniu 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) 

Answer 2

Th to może pomóc:

 
eln(x) = x 

i

 
(lm)n = lm*n 

Answer 3

Patrz Stirling's Approximation: (! n)

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

gdzie 2 ostatnie hasła są mniej znaczące niż pierwsze.

Answer 4

Przyczyniają się dalej, gdzie Mick Sharpe opuścił cię:

Nadszedł deriveration jest dość prosta: zobaczyć http://en.wikipedia.org/wiki/Logarithm -> teoria grup

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

Myśl n jako nieskończenie duża. Co to jest nieskończony minus jeden? lub minus dwa? itp.

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

A potem myśleć inf jak n.

Answer 5

http://en.wikipedia.org/wiki/Stirling%27s_approximation Przybliżenie Stirlinga może ci pomóc. Jest to naprawdę pomocne w radzeniu sobie z problemami na silniach związanych z ogromną liczbą rzędu 10^10 i więcej.

Answer 6

Zdaję sobie sprawę, że jest to bardzo stara sprawa z przyjętą odpowiedzi, ale żadna z tych odpowiedzi faktycznie korzysta z koncepcją zaproponowaną przez podpowiedź.

Jest to bardzo proste argumentu:

n! (= 1 * 2 * 3 * ... * n) jest iloczynem liczb każdego n mniej niż lub równe n. Dlatego jest on mniejszy niż iloczyn liczby n równej liczbie n; tj. n^n.

Połowa z liczb - tj. n/2 z nich - w produkcie n! jest większa lub równa n/2. Dlatego ich produkt jest większy niż produkt o numerach n/2 równy n/2; tj. (n/2)^(n/2).

Wykonaj logi, aby ustalić wynik.

Answer 7

Dzięki, znalazłem swoje 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) 

celu zweryfikowania problemu znalazłem to sieci, gdzie trzeba cały proces wyjaśnił: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

Answer 8

Na 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 = log n - 1)

połączenie obu granic:

1/2 (N LG N - 1) < = lg < = n log n

Wybierając dolna granica stałej większa niż (1/2) my (n!) może skompensować -1 wewnątrz wspornika.

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

Answer 9

Niestety, nie wiem jak używać składni LaTeX na StackOverflow ..