Es log (n!) = Θ(n * log (n))?
Voy a mostrar que log (n!) = Θ(n·log(n)).
Una sugerencia que me debe mostrar el límite superior con nn 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 nn a n·log(n) (es decir, registro de ambos lados de una ecuación), pero eso es una especie de trabajo hacia atrás.
¿Cuál sería el enfoque correcto para abordar este problema? Debo dibujar el árbol de recursión? No hay nada recursivo en esto, por lo que no parece un enfoque probable..
9 answers
Recuerda que
log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)
Puede 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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-03-04 00:38:43
Me doy cuenta de que esta es una pregunta muy antigua con una respuesta aceptada, pero ninguna de estas respuestas en realidad 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 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 in en el producto n! 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 para establecer el resultado.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-11-03 04:01:12
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.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-05-03 05:08:03
Para el 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)
Al elegir la constante de límite inferior mayor que (1/2) podemos compensar -1 dentro del corchete.
Así lg (n!) = Theta (n lg n)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-02-21 03:05:31
Lo siento, no se como usar la sintaxis LaTeX en stackoverflow..
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-01-10 21:56:54
Ayudándote aún más, donde Mick Sharpe te dejó:
Su burla es bastante simple: véase 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? sucesivamente.
Log(inf) + log(inf) + log(inf) + ... = inf * log (inf)
Y luego pensar en inf como n.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-01-19 18:25:58
Gracias, encontré sus 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 encontré esta web, donde tienes todo el proceso explicado: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-03-21 09:12:44
Esto podría ayudar:
eln(x) = x
Y
(lm)n = lm*n
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-01-21 08:42:49
Http://en.wikipedia.org/wiki/Stirling%27s_approximation La aproximación de Stirling podría ayudarte. Es realmente útil en el tratamiento de problemas en factoriales relacionados con grandes números del orden de 10^10 y por encima.
