big o - resueltos - ¿Qué es O(log(n!)) Y O(n!) Y la aproximación de Stirling

numeros de stirling ejercicios resueltos

Question

¿Qué es O(log(n!)) Y O(n!) ? Creo que es O(n log(n)) y O(n^n) ? ¿Por qué?

Creo que tiene que ver con la aproximación de Stirling, pero no recibo la explicación muy bien.

¿Alguien podría corregirme si me equivoco (sobre O(log(n!) = O(n log(n)) )? Y, si es posible, las matemáticas en términos más simples. realidad solo quiero una idea de como funciona esto

Answer 1

Por la aproximación de Stirling,

log(n!) = n log(n) - n + O(log(n))

Para n grande, el lado derecho está dominado por el término n log (n). Eso implica que O (log (n!)) = O (n log (n)).

Más formalmente, una definición de "O grande" es que f (x) = O (g (x)) si y solo si

lim sup|f(x)/g(x)| < ∞ as x → ∞

Usando la aproximación de Stirling, es fácil mostrar que log (n!) = O (n log (n)) usando esta definición.

Un argumento similar se aplica a n !. Para n grande, su comportamiento es muy parecido a n ^ n.

Answer 2

O(n!) No es equivalente a O(n^n) . Es asintóticamente menor que O(n^n) .

O(log(n!)) Es igual a O(n log(n)) . Aquí hay una manera de probar que:

Tenga en cuenta que al usar la regla de log(mn) = log(m) + log(n) podemos ver que:

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

Prueba de que O(log(n!)) ⊆ O(n log(n)) :

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

Que es menos que:

log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)

Entonces O(log(n!)) Es un subconjunto de O(n log(n))

Prueba de que O(n log(n)) ⊆ O(log(n!)) :

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

Que es mayor que (la mitad izquierda de esa expresión con todos (nx) reemplazados por n/2 :

log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2)) ∈ O(n log(n))

Entonces O(n log(n)) es un subconjunto de O(log(n!)) .

Dado que O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n)) , son clases equivalentes de big-Oh.