Это лог(n!) = Θ(n·log (n))?

Question

Это лог(n!) = Θ(n·log (n))?

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

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

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

9 174

mathjax algorithm big-o complexity-theory recursion

9 ответов:

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

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

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

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

возьмите журналы во всем, чтобы установить результат.

33

посмотреть приближение Стирлинга:

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

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

11

для нижней границы,
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)

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

таким образом lg (n!) = Тета (n lg n)

5

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

4

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

Это Деривация довольно проста: см.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 как infinitly большая. Что такое бесконечный минус один? или минус два? так далее.

log(inf) + log(inf) + log (inf) + ... = бесконечность * журнал(РСМД)

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

3

Спасибо, я нашел ваши ответы убедительными, но в моем случае, я должен использовать Θ свойства:
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

2

Это может помочь:
e^ln(x) = x
и
(l^m)ⁿ = l^m*n

1

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

0

Mick · Accepted Answer · 2018-03-04 02:38:43

помните, что
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) 