Quora User dio una respuesta que encontré bastante simple e intuitiva. Permítame hacer nuestra vida un poco más difícil usando la aproximación Stirling y proceder a partir de ella:
- La aproximación de Stirling indica que la [matemática] n! [/ math] se puede aproximar usando la siguiente fórmula [math] n! = \ sqrt {2 \ pi n} \ frac {n} {e} ^ n [/ math] que se puede simplificar a lo siguiente
[math] n! = \ frac {\ sqrt {2 \ pi}} {e ^ n} \ sqrt {n} n ^ n [/ math] Esto podría simplificarse aún más para ser como el siguiente,
[matemáticas] n! = \ frac {\ sqrt {2 \ pi}} {e ^ n} n ^ {n + \ frac {1} {2}} [/ matemáticas] - Del último paso, y al tomar [math] log [/ math] para ambos lados, obtenemos lo siguiente:
[matemáticas] \ log (n!) = \ log {\ frac {\ sqrt {2 \ pi}} {e ^ n} n ^ {n + \ frac {1} {2}}} [/ math] - usando reglas logarítmicas básicas para simplificar aún más la última ecuación, obtenemos
- [matemáticas] \ log {n!} = \ log {\ frac {\ sqrt {2 \ pi}} {e ^ n} n ^ {n + \ frac {1} {2}}} = \ log {\ frac { \ sqrt {2 \ pi}} {e ^ n}} + (n + \ frac {1} {2}) \ log {n} = \ log {\ sqrt {2 \ pi}} – \ log {e ^ n } + n ^ {n + \ frac {1} {2}} = \ log {{\ sqrt {2 \ pi}}} – n + (n + \ frac {1} {2}) \ log {n} [/ math ] [matemática] [/ matemática] La forma final de la fórmula después de la reducción y todo será el siguiente:
[matemáticas] \ log {n!} = \ log {\ sqrt {2 \ pi}} – n + (n + \ frac {1} {2}) \ log {n} [/ math] - Aparte de lo anterior, si tenemos dos funciones [matemática] f (n) [/ matemática] y [matemática] g (n) [/ matemática] y es necesario comparar el crecimiento de cada función, es decir, g [matemática] (n) = O (f (n)) [/ matemáticas], g [matemáticas] (n) = \ Theta (f (n)) [/ matemáticas] o g [matemáticas] (n) = \ Omega (f ( n)) [/ math], lo hacemos examinando la función cuando la entrada es lo más alta posible, es decir, [math] n \ rightarrow \ infty [/ math]
[matemáticas] x = \ lim_ {n \ rightarrow \ infty} \ frac {g (n)} {f (n)} [/ math] Tenemos tres escenarios básicos
Caso 1 : [matemáticas] x = 0 [/ matemáticas] lo que significa que el crecimiento de la función [matemáticas] f (n) [/ matemáticas] es mayor que [matemáticas] g (n) [/ matemáticas], es decir, [matemáticas ] g (n) = O (f (n)) [/ matemáticas]
Caso 2 : x [matemática] = constante [/ matemática] lo que significa que el crecimiento de ambas funciones es el mismo, y por lo tanto el valor constante, es decir, [matemática] g (n) = \ Theta (f (n)) [ /matemáticas]
Caso 3 : x [matemática] = \ infty [/ matemática] lo que significa que [matemática] f (n) [/ matemática] es superada por [matemática] g (n) [/ matemática], es decir [matemática] g (n ) = \ Omega (f (n)) [/ matemáticas] - De vuelta a donde nos detuvimos, que era
[math] \ log {n!} = \ log {\ sqrt {2 \ pi}} – n + (n + \ frac {1} {2}) \ log {n} [/ math] Aquí, supongamos que la solución es de hecho [matemáticas] \ Theta {(n \ log {n})} [/ matemáticas], y de acuerdo con lo que se indicó anteriormente en el punto 4, las [matemáticas] \ lim_ {n \ rightarrow \ infty} \ frac {g (n )} {f (n)} [/ math] debe ser constante, si nuestra suposición es correcta.
[matemáticas] \ lim_ {n \ rightarrow \ infty} \ frac {\ log {\ sqrt {2 \ pi}} – n + (n + \ frac {1} {2}) \ log {n}} {n \ log { n}} = 0- \ frac {1} {\ log {n}} + 1+ \ frac {\ frac {1} {2}} {n \ log {n}} = 1 [/ math] que concluye que [matemáticas] \ log {n!} = \ Theta (n \ log {n}) [/ matemáticas]
Bueno, eso es todo. Si puedo, me gustaría recomendar este libro para leer más.