algorithm - for - ¿Es log(n!)=Θ(n · log(n))?

big o notation properties

Question

Debo mostrar que log ( n !) = Θ ( n · log ( n )) .

Se dio una pista 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 ⁿ en n · log ( n ) (es decir, registrar ambos lados de una ecuación), pero eso es como retroceder.

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

Answer 1

Esto podría ayudar:

e^ln(x) = x

y

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

Answer 2

Gracias, encontré tus respuestas convincentes, pero en mi caso, debo usar las propiedades Θ :

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

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

Answer 3

Me doy cuenta de que esta es una pregunta muy antigua con una respuesta aceptada, pero ninguna de estas respuestas realmente utiliza el enfoque sugerido por la sugerencia.

Es un argumento bastante simple:

n! (= 1 * 2 * 3 * ... * n) es un producto de n números cada uno menor que 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 n! producto son mayores o iguales a 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 a lo largo para establecer el resultado.

Answer 4

Para un 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)

Combinando ambos límites:

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

Al elegir una constante de límite inferior superior a (1/2) podemos compensar por -1 dentro del paréntesis.

Por lo tanto, lg (n!) = Theta (n lg n)

Answer 5

Recuerda eso

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

Puedes obtener el límite superior por

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

Y puedes 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 6

Te ayudamos a seguir, donde Mick Sharpe te dejó:

Su derivación es bastante simple: ver http://en.wikipedia.org/wiki/Logarithm -> Teoría de grupos

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

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

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

Y luego piensa en inf como n.

Answer 7

Ver la aproximación de Stirling :

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

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

Answer 8

http://en.wikipedia.org/wiki/Stirling%27s_approximation La aproximación de Stirling podría ayudarte. Es realmente útil para tratar problemas en factoriales relacionados con números enormes del orden de 10 ^ 10 y superiores.

Answer 9

Lo siento, no sé cómo usar la sintaxis LaTeX en .