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

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

Было дано указание, что я должен показать верхнюю границу с n ⁿ и показать нижнюю границу с (n/2) ^(n/2). Это кажется мне неинтересным. Почему это так? Я могу определенно увидеть, как преобразовать n ⁿ в n · log (n) (т.е. Записывать обе стороны уравнения), но этот вид работы обратный.

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

Ответы

Ответ 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)

Ответ 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).

Взять журналы для установления результата.

Ответ 3

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

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

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

Ответ 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

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

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

Ответ 5

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

Ответ 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)

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

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

А потом подумайте о inf как n.

Ответ 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

Ответ 8

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

e^ln(x) = x

(l^m)ⁿ = l^m*n

Ответ 9

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

Ответ 10

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