Является ли log (n!) = Θ (n · log (n))?

Question

Я должен показать, что log ( n !) = Θ ( n · log ( n )) .

Намек был дан, что я должен показать верхнюю границу с n ⁿ и показать нижнюю границу с (* 1 020 * N / 2) * * тысячу двадцать-два ( N / 2) * 1 026 *. Это не кажется мне таким уж интуитивным. Почему это так? Я определенно вижу, как конвертировать n ⁿ в n · log ( n ) (т. е. записать обе части уравнения), но это работает в обратном направлении.

Каков будет правильный подход к решению этой проблемы? Должен ли я нарисовать рекурсивное дерево? В этом нет ничего рекурсивного, так что это не похоже на вероятный подход ..

Answer 1

Помните, что

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

Вы можете получить верхнюю границу на

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

И вы можете получить нижнюю границу, выполнив аналогичные действия после выброса первой половинысумма:

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

Я понимаю, что это очень старый вопрос с принятым ответом, но ни один из этих ответов не использует подход, предложенный подсказкой.

Это довольно простой аргумент:

n! (= 1 * 2 * 3 * ... * n) является произведением n чисел, каждое из которых меньше или равно n. Следовательно, оно меньше произведения n чисел, равных n; то есть n^n.

Половина чисел - то есть n/2 из них - в произведении n! больше или равно n/2. Следовательно, их произведение больше, чем произведение чисел n/2, равных n/2; то есть (n/2)^(n/2).

Принимайте логи повсюду, чтобы установить результат.

Answer 3

См. Приближение Стирлинга :

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

, где последние 2 термина менее значимы, чем первый.

Answer 4

Для нижней границы,

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)

Объединение обеих границ:

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

Выбрав нижнюю граничную константу больше (1/2), мы можем компенсировать -1 внутри скобки.

Таким образом, lg (n!) = Theta (n lg n)

Answer 5

Извините, я не знаю, как использовать синтаксис LaTeX в stackoverflow ..

Answer 6

Помогая вам дальше, где Мик Шарп оставил вас:

Это довольно просто: см http://en.wikipedia.org/wiki/Logarithm -> Теория групп

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

Подумайте как бесконечно большой . Что такое бесконечный минус один? или минус два? и т.д.

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

А затем представьте inf как n.

Answer 7

Спасибо, я нашел ваши ответы убедительными, но в моем случае я должен использовать свойства Θ :

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

, чтобы проверить проблему, я нашел эту сеть, где вы объяснили весь процесс: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

Answer 8

Это может помочь:

e<sup>ln(x)</sup> = x

и

(l<sup>m</sup>)<sup>n</sup> = l<sup>m*n</sup>

Answer 9

http://en.wikipedia.org/wiki/Stirling%27s_approximation Приближение Стирлинга может вам помочь.Это действительно полезно при решении проблем факториалов, связанных с огромными числами порядка 10 ^ 10 и выше.