¿Es cierto que digo que O ((log n)!) Y O (n!) Son iguales?

Answer 1

No. [math] f (n) = n! [/ Math] es una función que obviamente es [math] O (n!) [/ ​​Math] pero no es [math] O ((\ log n)!) [/matemáticas]

Supongamos que así fuera, para algunos [matemática] n_0 [/ matemática] y [matemática] c> 1 [/ matemática] la desigualdad [matemática] n! \ leq c (\ log n)! [/ math] se mantiene para [math] n \ geq n_0 [/ math]. (Esta es la definición de notación big-O, no “qué son cuando n es infinito”.) Elija [math] n = e ^ {cn_0} [/ math]. Entonces [matemáticas] (e ^ {cn_0})! \ leq c (cn_0)! [/ math]. Pero eso es obviamente falso, [math] e ^ {cn_0} [/ math] es mucho más grande que [math] cn_0 [/ math]. (Hacer que esto sea hermético y eliminar ese factor de c requiere un poco más de trabajo).

Creo que su pregunta de seguimiento es si [math] (\ log n)! [/ Math] está polinómicamente acotada. Obviamente no es un polinomio en sí mismo. La aproximación de Stirling nos da

[matemáticas] n! \ leq es ^ {n + 1/2} e ^ {- n} [/ math]

Entonces,

[matemáticas] (\ log n)! \ leq e (\ log n) ^ {1/2 + \ log n} e ^ {- \ log n} [/ math]

Ahora [matemáticas] (\ log n) ^ {\ log n} = (e ^ {\ log \ log n}) ^ {\ log n} = e ^ {(\ log n) \ cdot (log \ log n) }[/matemáticas]

Entonces, el orden de crecimiento es aproximadamente [matemático] e ^ {(\ log n) (\ log \ log n) – \ log n} = n ^ {(\ log \ log n) – 1} [/ matemático]

Desafortunadamente, esto no está limitado por ningún polinomio, ya que [math] \ log \ log n [/ math] eventualmente excederá cualquier número entero positivo.

Por ejemplo, compare [math] (\ log n)! [/ Math] con [math] n ^ 2 [/ math].

En [matemáticas] n = e ^ {10}, (\ log n)! = 348 [/ matemáticas] 0, mientras que [matemáticas] (e ^ {10}) ^ 2 \ aprox 4.85 \ veces 10 ^ 8 [/ matemáticas]

En [matemáticas] n = e ^ {100}, (\ log n)! \ aproximadamente 10 ^ {157} [/ matemáticas], mientras que [matemáticas] e ^ {200} \ aproximadamente 10 ^ {86} [/ matemáticas]

Entonces en algún punto intermedio se cruzan. 🙂

Answer 2

Para tener una idea general acerca de qué tan rápido crece [math] (\ log n)! [/ Math], puede darse cuenta de que el término más importante de la aproximación del factorial de Stirling es [math] n ^ n [/ math], así que en este caso estamos tratando con algo como [matemáticas] O (({\ log n}) ^ {\ log n}) [/ matemáticas] (con algunos factores adicionales que lo hacen un poco más pequeño, por lo que esto no es [ matemáticas] \ Theta () [/ matemáticas]).

Así que veamos rápidamente qué tan grande es esto:

[matemáticas] ({\ log n}) ^ {\ log n} = e ^ {\ log \ log n \ cdot \ log n} = e ^ {\ log n \ cdot \ log \ log n} = n ^ { \ log \ log n} [/ math]

Por lo tanto, crece más rápido que cualquier polinomio, pero apenas así, ya que el exponente apenas está creciendo. Es mucho más pequeño que [math] e ^ n, [/ math] y mucho menos [math] n! [/ Math].

Answer 3

Puede compararlos aproximadamente aplicando la aproximación de Stirling.

[matemáticas] O (\ log (n)!) = n ^ {O (\ log \ log (n))} [/ matemáticas]

[matemáticas] O (n!) = n ^ {O (n)} [/ matemáticas]

Entonces, el primero es definitivamente más grande que cualquier polinomio, pero definitivamente está por debajo del segundo.

Answer 4

No. En general, [math] log (n)

Answer 5

No claro que no. La función [matemática] f (n) = n [/ matemática] es [matemática] O (n) [/ matemática] pero no [matemática] O (\ log n) [/ matemática]. Del mismo modo, [math] g (n) = n! [/ Math] es [math] O (n!) [/ ​​Math] pero no [math] O ((\ log n)!) [/ ​​Math].

Answer 6

A2A: Bien puede ser cierto que lo dices ; pero eso no lo hace verdad. De hecho, es falso. Tampoco es polinomial. Su argumento basado en “cuando [matemáticas] n [/ matemáticas] es infinito” no tiene sentido. Debe abordar las proporciones en el límite cuando [math] n [/ math] se acerca al infinito.

Answer 7

Gracias por el A2A! En primer lugar, tengo que estar de acuerdo con los otros coroanos que han respondido a esta pregunta. Me gustaría interponer un pensamiento:

Si bien la entrada de la notación grande de octubre está en el ámbito de los enteros positivos, la salida está en los Reales. Esto es importante porque la función factorial no existe en el espacio Reals, pero tiene la función Gamma, que se ha demostrado que se reduce a la función factorial en los enteros.

Eso probablemente no ayude, ¡pero espero que sí!

¡Buena suerte!

Answer 8

Como n -> (+ ve infinito), log (n) = (+ ve infinito).

Entonces, asintóticamente, es decir, O ((log n)!) = O ((+ ve infinity)!)

Ahora, mirando f (n) = n, O (n!) = O ((+ ve infinity)!)

Veamos ahora con más detalle, si estos infinitos escalan de manera diferente o similar.

La relación entre dos funciones (log ny n) es (e ^ x / x).

La aplicación del límite de (+ ve infinito) conducirá a una forma indeterminada.

Ahora necesitamos aplicar la regla de L’Hôpital.

Entonces la relación se reducirá a e ^ x / 1.

Esto siempre mantendrá la segunda función de costo dada más alta y, por lo tanto, diferente de la primera.