¿Es log (n!) = Θ (n · log (n))?

Question

estoy para demostrar que log (n !) = Θ (n · log (n )).

Se dio un indicio de que debería mostrar el límite superior con nⁿ y mostrar el límite inferior con (n/2) ^(n/2) . Esto no me parece tan intuitivo. ¿Por qué sería ese el caso? Definitivamente puedo ver cómo convertir nⁿ a n · log (n ) (es decir, log ambos lados de una ecuación), pero eso es algo de trabajar hacia atrás.

¿Cuál sería el enfoque correcto para abordar este problema? ¿Debería dibujar el árbol de recursión? No hay nada acerca de este recursivo, por lo que no parece ser un enfoque probable ..

Answer 1

Recuerde que

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

que pueda obtener el límite superior por

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

y se puede obtener el límite inferior haciendo algo similar después de tirar la primera mitad de la suma:

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 se podría ayudar:

 
eln(x) = x 

y

 
(lm)n = lm*n 

Answer 3

Ver Stirling's Approximation: (n)

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

donde los últimos 2 términos son menos importantes que el primero.

Answer 4

que ayuda aún más, cuando Mick Sharpe le dejó:

Es deriveration es bastante simple: ver http://en.wikipedia.org/wiki/Logarithm -> Teoría de Grupos

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

Think de n como infinitamente grande. ¿Qué es infinito menos uno? o menos dos? etc.

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

Y luego pensar en inf como n.

Answer 5

http://en.wikipedia.org/wiki/Stirling%27s_approximation Stirling Approximation puede ser útil. Es realmente útil para tratar problemas en factoriales relacionados con números enormes del orden de 10^10 y superiores.

Answer 6

Comprendo que esto es una pregunta muy antigua con una respuesta aceptada, pero ninguna de estas respuestas realmente utilizan el enfoque sugerido por la indirecta.

es un argumento bastante simple:

n! (= 1 * 2 * 3 * ... * n) es un producto de n números de cada menor o igual a n. Por lo tanto, es menor que el producto de n números todos iguales a n; es decir, n^n.

La mitad de los números - es decir, n/2 de ellos - en el producto n! son mayores o iguales que n/2. Por lo tanto, su producto es mayor que el producto de n/2 números todos iguales a n/2; es decir, (n/2)^(n/2).

Tome registros en todas partes para establecer el resultado.

Answer 7

Gracias, lo encontraron sus respuestas convincentes pero en mi caso, deben utilizar los Θ propiedades:

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

para verificar el problema que encontré esta web, donde usted tiene todo el proceso explicado: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

Answer 8

Para límite inferior,

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)

La combinación de ambos límites:

media (n lg n - 1) = < lg < = n lg n

Al elegir límite inferior constante mayor que (1/2) nosotros (n!) puede compensar por -1 dentro del soporte.

Así lg (n!) = Theta (n lg n)

Answer 9

Lo sentimos, no sé cómo utilizar la sintaxis de látex en stackoverflow ..