Complejidad de tiempo de 2 ^ sqrt (n)

11

Estoy resolviendo una pregunta de algoritmo y mi análisis es que se ejecutaría en O (2 ^ sqrt (n)). ¿Como de grande es? ¿Equivale a O (2 ^ n)? ¿Sigue siendo tiempo no polinómico?

Gaara
fuente
3
Por favor comente la razón por la cual se rechaza la votación. ¡Gracias!
Gaara
44
Honestamente, sospecho que la gente está confundiendo esto con una pregunta extremadamente trivial, pero no es inmediatamente obvio para mí cómo probarlo de cualquier manera, así que iré a escribir una respuesta y veré si eso cambia las mentes de las personas.
Ixrec
3
Tiempo sub-exponencial, segunda definición, de acuerdo con el artículo de Wikipedia (Descargo de responsabilidad: no voté en contra, y no sé lo suficiente sobre este tema para decir si esto es correcto o no.)
rwong
1
¡Excelente! Tiempo subexponencial: "el tiempo de ejecución de algún algoritmo puede crecer más rápido que cualquier polinomio, pero sigue siendo significativamente menor que un exponencial". Esto definitivamente responde a mi pregunta y amplía mi conocimiento sobre el análisis Big O. Muchas gracias
Gaara
1
Es mucho menor que O (2 ^ n), especialmente para grandes números. Tome un ejemplo de tener una colección de 10 000 elementos. 2 ^ 10000 es un número con aproximadamente 3000 dígitos, esa es la cantidad de ciclos que se necesitarían para realizar una operación O (2 ^ n) en él. Con O (2 ^ sqrt (n)) estás en un número con 30 dígitos. La diferencia es extremadamente grande para grandes números a favor de la solución sqrt (para 1 millón de elementos que son (número con 300 000 dígitos) * ciclo de la CPU versus (número con 300 dígitos) * ciclo de la CPU).
Andy

Respuestas:

16

Esta es una pregunta interesante. Afortunadamente, una vez que sabes cómo resolverlo, no es particularmente difícil.

Para las funciones f : NR + y g : NR + , tenemos fO ( g ) si y sólo si sup lim n → ∞ f ( n ) / g ( n ) ∈ R .

Una función f : NR + tiene a lo sumo crecimiento polinómico si y solo si existe una constante kN tal que fO ( nn k ). Vamos a resolver esto para kN arbitrario pero fijo .

lim sup n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ e log (2) n 1/2 / e log ( n ) k =
lim n → ∞ e log (2) n 1/2 - log ( n ) k = ∞ ∉ R

La primera igualdad es verdadera porque ambos, el nominador y el denominador, son funciones estables que crecen monotónicamente. La segunda igualdad usa la identidad x y = e log ( x ) y . El límite no es finito porque el exponente en la expresión final no está limitado anteriormente. Sin dar una prueba formal, se puede suponer que se sabe que n 1/2 domina log ( n ) asintóticamente. Por lo tanto, la función en cuestión excede el crecimiento polinómico.

Sin embargo, su crecimiento es estrictamente menor que exponencial, donde exponencial se define (por mí, para este propósito) como O ( n ↦ 2 c n ) para c > 0. Mostrar esto es aún más directo.

lim sup n → ∞ 2 c n / 2 ( n 1/2 ) = lim n → ∞ 2 c n - n 1/2 = ∞ ∉ R

para cualquier c > 0. fijo . Por lo tanto, la complejidad de la función está en algún lugar verdaderamente entre polinomio y exponencial.

5gon12eder
fuente
6

¿Como de grande es? Bueno, O (2 ^ sqrt (n)) es exactamente lo grande que es :-(

Para tener una idea de lo que significa, imagine que su algoritmo no sería solo O (2 ^ sqrt (n)), sino que en realidad requiere exactamente 2 ^ sqrt (n) nanosegundos en su computadora:

n = 100: 2 ^ 10 = 1024 nanosegundos. No hay tiempo en absoluto. n = 1000: 2 ^ 31.xxx = 2 mil millones de nanosegundos. Dos segundos, eso se nota. n = 10,000: 2 ^ 100 ≈ 10 ^ 30 nanosegundos = 10 ^ 21 segundos = 30 trillones de años.

Esto es mucho mejor que 2 ^ n nanosegundos, donde n = 100 tomaría 30 billones de años, pero aún así el tamaño de los problemas que puede resolver es bastante limitado. Si considera un problema "solucionable" si su computadora puede resolverlo en una semana, eso es aproximadamente 6 x 10 ^ 14 nanosegundos, eso es aproximadamente n = 2,400. Por otro lado, hasta n = 400 se pueden resolver en un milisegundo.

(En la práctica, para n = 10,000, tanto O (2 ^ sqrt (n)) como O (2 ^ n) toman exactamente el mismo tiempo: demasiado tiempo para esperarlo).

Excede cualquier polinomio. Tome otro algoritmo que tome n ^ 1000 segundos. Lo cual es prácticamente insoluble para n = 2. Este algoritmo lleva más tiempo hasta que n es de aproximadamente 885 millones. Pero realmente, a quién le importa? En ese momento, el número de años que toman ambos algoritmos es un número de 9,000 dígitos.

gnasher729
fuente