Complejidad Exponencial

Complejidad exponencial - en la teoría de la complejidad de los algoritmos , la complejidad del problema, limitada por la exponencial del polinomio de la dimensión del problema, es decir, está limitada por la función , donde es algún polinomio, y es el tamaño del problema. En este caso, se dice que la complejidad del problema aumenta exponencialmente . A menudo, la complejidad se refiere al tiempo de ejecución de un algoritmo. En este caso, se dice que el algoritmo pertenece a la clase EXPTIME . Sin embargo, la complejidad también puede referirse a la memoria u otros recursos necesarios para que el algoritmo funcione. ${\ estilo de visualización \ exp (P (n))}$ $PAGS$ $norte$

La distinción entre algoritmos polinómicos y exponenciales se remonta a von Neumann . [una]

Complejidad del tiempo

Las tareas con complejidad de tiempo de ejecución exponencial forman la clase EXPTIME , definida formalmente como:

{\text{EXPTIME}}=\bigcup _{k=1}^{\infty }TIME\left(2^{n^{k}}\right)

donde es el conjunto de problemas que pueden resolverse mediante algoritmos cuyo tiempo de ejecución está acotado superiormente por la función . $TIEMPO(f(n))$ $pie)$

Comparación con la complejidad polinomial

En general, se acepta que los algoritmos con complejidad polinomial son "rápidos", mientras que los algoritmos con una complejidad mayor que la polinomial son "lentos". Desde este punto de vista, los algoritmos con complejidad exponencial son lentos. Sin embargo, esta suposición no es del todo exacta. El hecho es que el tiempo de ejecución del algoritmo depende del valor de n (la dimensión del problema) y las constantes relacionadas ocultas en la notación O. En algunos casos, para valores pequeños de n , el tiempo polinomial puede exceder al tiempo exponencial. Sin embargo, para valores grandes de n , el tiempo de ejecución del algoritmo con complejidad exponencial es mucho mayor.

Complejidad subexponencial

Hay algoritmos que se ejecutan en un tiempo superior al polinomial ( "superpolinomio" ), pero inferior al tiempo exponencial ( "subexponencial" ). Un ejemplo de tal problema es la factorización de un número entero en factores primos ( factorización ). Dichos algoritmos también se denominan "lentos".

Véase también

clase EXPTIME
O notación
tiempo constante
tiempo lineal
Problema completo NP

Notas

↑ John von Neumann. Cierto juego de suma cero para dos personas equivalente al problema de asignación óptima // Contribuciones a la teoría de los juegos / HW Kuhn , AW Tucker , Eds. — Princeton, Nueva Jersey: Universidad de Princeton. Prensa , 1953. - P. 5-12. — 404 pág.