¿Es log(n!) = Θ(n·log(n))?
Debo mostrar que log( n !) = Θ( n ·log( n )) .
Se me dio una pista de que debería mostrar el límite superior con n 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 n en n ·log( n ) (es decir, registrar ambos lados de una ecuación), pero eso es algo así como trabajar al revés.
¿Cuál sería el enfoque correcto para abordar este problema? ¿Debo dibujar el árbol de recursividad? No hay nada recursivo en esto, por lo que no parece un enfoque probable.
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 desechar 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)
Me doy cuenta de que esta es una pregunta muy antigua con una respuesta aceptada, pero ninguna de estas respuestas utiliza el enfoque sugerido por la sugerencia.
Es un argumento bastante simple:
n!(= 1*2*3*...*n) es un producto de nnúmeros cada uno menor o igual a n. Por lo tanto es menor que el producto de nnúmeros todos iguales a n; es decir, n^n.
La mitad de los números (es decir, n/2de ellos) del n!producto son mayores o iguales que n/2. Por lo tanto su producto es mayor que el producto de n/2números todos iguales a n/2; es decir (n/2)^(n/2).
Tome registros para establecer el resultado.
