Complejidad temporal
En informática, la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que lleva ejecutar un algoritmo. La complejidad temporal se estima comúnmente contando el número de operaciones elementales realizadas por el algoritmo, suponiendo que cada operación elemental requiere una cantidad fija de tiempo. Por lo tanto, la cantidad de tiempo necesario y el número de operaciones elementales realizadas por el algoritmo difieren en un factor constante como máximo.
Dado que el tiempo de ejecución de un algoritmo puede variar entre diferentes entradas del mismo tamaño, comúnmente se considera la complejidad temporal del peor caso, que es la cantidad máxima de tiempo requerida para las entradas de un tamaño determinado. Menos común, y usualmente especificado explícitamente, es la complejidad del caso promedio, que es el promedio del tiempo necesario para las entradas de un tamaño dado (esto tiene sentido porque solo hay un número finito de entradas posibles de un tamaño dado). En ambos casos, la complejidad temporal generalmente se expresa como una función del tamaño de la entrada. Dado que esta función es generalmente difícil de calcular exactamente, y el tiempo de ejecución para entradas pequeñas generalmente no es consecuente, uno comúnmente se enfoca en el comportamiento de la complejidad cuando aumenta el tamaño de entrada, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad temporal se expresa comúnmente usando la notación O grande, típicamente etc., donde n es el tamaño de entrada en unidades de bits necesarios para representar la entrada.
Las complejidades algorítmicas se clasifican según el tipo de función que aparece en la notación O grande. Por ejemplo, un algoritmo con complejidad temporal es un algoritmo de tiempo lineal y un algoritmo con complejidad de tiempo por alguna constante es un algoritmo de tiempo polinómico .
La siguiente tabla resume algunas clases de complejidades de tiempo comúnmente encontradas. En la tabla, poly(x) = xO(1), es decir, polinomial en x .
Se dice que un algoritmo es tiempo constante (también escrito como tiempo O(1)) si el valor de T(n) está limitado por un valor que no depende del tamaño de la entrada. Por ejemplo, acceder a cualquier elemento individual en una matriz requiere tiempo constante, ya que solo se debe realizar una operación para localizarlo. De manera similar, encontrar el valor mínimo en una matriz ordenada en orden ascendente también es una operación de tiempo constante ya que el resultado es siempre el primer elemento. Sin embargo, encontrar el valor mínimo en una matriz desordenada no es una operación de tiempo constante ya que es necesario escanear cada elemento de la matriz para determinar el valor mínimo. Por lo tanto, este caso es una operación de tiempo lineal, que toma tiempo O(n). Sin embargo, si el número de elementos se conoce de antemano y no cambia aún se puede decir que dicho algoritmo se ejecuta en tiempo constante.
A pesar del nombre "tiempo constante", el tiempo de ejecución no tiene que ser independiente del tamaño del problema, pero un límite superior para el tiempo de ejecución tiene que estar limitado independientemente del tamaño del problema. Por ejemplo, la tarea "intercambia los valores de a y b si es necesario para que a ≤ b " se llama de tiempo constante aunque el tiempo pueda depender de si ya es cierto o no que a ≤ b . Sin embargo, hay una constante t tal que el tiempo requerido es siempre como máximo t .
Estos son algunos ejemplos de fragmentos de código que se ejecutan en tiempo constante. :
Si T(n) es O(cualquier valor constante) se indica en notación estándar como T(n) siendo O(1).
Se dice que un algoritmo toma tiempo logarítmico cuando T(n) = O(log n) . Dado que log a n y log b n están relacionados por un multiplicador constante, y dicho multiplicador es irrelevante para la clasificación big-O, el uso estándar para algoritmos de tiempo logarítmico es O(log n ) independientemente de la base del logaritmo que aparece en la expresión de T.
Los algoritmos que toman tiempo logarítmico se encuentran comúnmente en operaciones con árboles binarios o cuando se usa la búsqueda binaria.
Un algoritmo O(log n) se considera altamente eficiente, ya que la relación entre el número de operaciones y el tamaño de la entrada disminuye y tiende a cero cuando aumenta n. Un algoritmo que debe acceder a todos los elementos de su entrada no puede tomar tiempo logarítmico ya que el tiempo necesario para leer una entrada de tamaño n es del orden de n .
Un ejemplo de tiempo logarítmico es la búsqueda dentro de un diccionario. Considere un diccionario D que contiene n entradas, ordenadas por orden alfabético. Suponemos que, para 1 ≤ k ≤ n, uno puede acceder a la entrada k del diccionario en un tiempo constante. Usemos D(k) para denotar la k-ésima entrada. Bajo estas hipótesis, la prueba de si una palabra w está en el diccionario se puede hacer en tiempo logarítmico: considere dónde denota la función de piso . Si entonces hemos terminado. Si no continuamos la búsqueda de la misma manera en la mitad izquierda del diccionario, de lo contrario continuamos de manera similar con la mitad derecha del diccionario. Este algoritmo es similar al método utilizado a menudo para encontrar una entrada en un diccionario de papel.
Se dice que un algoritmo se ejecuta en tiempo poli-logarítmico si T(n) = O ((log n )k ), para alguna constante k. Por ejemplo, el orden de una matriz de cadena se puede resolver en tiempo poli-logarítmico en una máquina paralela de acceso aleatorio.
Se dice que un algoritmo se ejecuta en tiempo sub-lineal si T(n)=o(n). En particular, esto incluye algoritmos con las complejidades de tiempo definidas anteriormente.
Los algoritmos típicos que son exactos y, sin embargo, se ejecutan en tiempo sub-lineal usan el procesamiento paralelo (como lo hace el cálculo del determinante de una matriz NC1), o alternativamente tienen suposiciones garantizadas en la estructura de entrada (como lo hacen la búsqueda binaria de tiempo logarítmico y muchos algoritmos de mantenimiento de árboles). Sin embargo, los lenguajes formales, como el conjunto de todas las cadenas que tienen un bit en la posición indicada por los primeros log (n) bits de la cadena pueden depender de cada bit de la entrada y, sin embargo, ser computables en tiempo sub-lineal.
El término específico algoritmo de tiempo sublineal generalmente se reserva a algoritmos que son diferentes a los anteriores en el sentido de que se ejecutan sobre modelos de máquinas seriales clásicas y donde no se permiten suposiciones previas en la entrada. Sin embargo, se les permite ser aleatorizados, y de hecho deben ser aleatorizados para todas las tareas excepto las más triviales.
Como tal, un algoritmo debe proporcionar una respuesta sin leer toda la entrada, sus detalles dependen en gran medida del acceso permitido a la entrada. Por lo general, para una entrada que se representa como una cadena binaria b1,..., bk se supone que el algoritmo puede solicitar y obtener el valor de bi para cualquier i en tiempo O(1).
Los algoritmos de tiempo sub-lineal suelen ser aleatorios y solo proporcionan soluciones aproximadas. De hecho, la propiedad de una cadena binaria que solo tiene ceros puede demostrarse fácilmente que no puede ser decidida por un algoritmo de tiempo sub-lineal (no aproximado). Los algoritmos de tiempo sub-lineales surgen naturalmente en la investigación de property testing .
Se dice que un algoritmo toma tiempo lineal, o tiempo O(n), si su complejidad temporal es O(n). Informalmente, esto significa que el tiempo de ejecución aumenta como máximo linealmente con el tamaño de la entrada. Más precisamente, esto significa que hay una constante c tal que el tiempo de ejecución es como máximo cn para cada entrada de tamaño n . Por ejemplo, un procedimiento que suma todos los elementos de una lista requiere un tiempo proporcional a la longitud de la lista, si el tiempo de adición es constante o, al menos, está limitado por una constante.
El tiempo lineal es la mejor complejidad de tiempo posible en situaciones en las que un algoritmo tiene que leer secuencialmente toda su entrada. Por lo tanto, se ha invertido mucha investigación en descubrir algoritmos que exhiben tiempo lineal o, al menos, tiempo casi lineal. Esta investigación incluye métodos de software y hardware. Hay varias tecnologías de hardware que explotan el paralelismo para proporcionar esto. Un ejemplo es la memoria direccionable por contenido . Este concepto de tiempo lineal se utiliza en algoritmos de coincidencia de cadenas como el algoritmo de Boyer-Moore y el algoritmo de Ukkonen .
Se dice que un algoritmo se ejecuta en tiempo cuasilineal (también denominado tiempo log-lineal) si T (n)=O(n log k n) para alguna constante positiva k; el caso de k=1 se llama tiempo linealitmico. Usando la notación O suave, estos algoritmos son Õ(n). Los algoritmos de tiempo cuasilineal también son O(n1+ε) para cada constante ε> 0, y por lo tanto se ejecutan más rápido que cualquier algoritmo de tiempo polinómico cuyo límite de tiempo incluye un término nc para cualquier c>1)
Los algoritmos que se ejecutan en tiempo cuasilineal incluyen:
En muchos casos, el tiempo de ejecución n log n es simplemente el resultado de realizar una operación Θ (log n) n veces. Por ejemplo, el ordenamiento de un árboles binario crea un árbol binario insertando uno por uno los elementos de la matriz de tamaño n. Dado que la operación de inserción en un árbol de búsqueda binaria auto-balanceado toma tiempo O(log n ), todo el algoritmo toma tiempo O (n log n).
El ordenamiento por comparación requiere al menos Ω(n log n) comparaciones en el peor de los casos porque log (n!) = Θ(n log n), por aproximación de Stirling. Esto tiempos también surgen con frecuencia de la relación de recurrencia T(n) = 2T(n/2) + O (n).
Se dice que un algoritmo es de tiempo subcuadrático si T (n) = O(n2).
Por ejemplo, los algoritmos de ordenamiento simples basados en la comparación son cuadráticos (por ejemplo, ordenamiento por inserción) pero se pueden encontrar algoritmos más avanzados que son subcuadráticos (por ejemplo, ordenamiento shell). Ningún algoritmo de ordenamiento de propósito general se ejecuta en tiempo lineal pero la reducción de un tiempo cuadrático a uno subcuadrático es de gran importancia práctica.
Se dice que un algoritmo es de tiempo polinómico si su tiempo de ejecución está limitado por una expresión polinómica en el tamaño de la entrada para el algoritmo, es decir, T (n) = O(nk) para alguna constante positiva k. Los problemas para los que existe un algoritmo de tiempo polinómico determinista pertenecen a la clase de complejidad P, que es central en el campo de la teoría de la complejidad computacional. La tesis de Cobham establece que el tiempo polinomial es sinónimo de "manejable", "factible", "eficiente" o "rápido".
Algunos ejemplos de algoritmos de tiempo polinomiales:
En algunos contextos, especialmente en la optimización, uno diferencia entre el tiempo fuertemente polinomial y los algoritmos de tiempo débilmente polinomial . Estos dos conceptos solo son relevantes si las entradas a los algoritmos consisten en enteros.
El tiempo fuertemente polinómico se define en el modelo aritmético de computación. En este modelo de computación, las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) toman un paso de unidad de tiempo para realizar, independientemente de los tamaños de los operandos. El algoritmo se ejecuta en tiempo fuertemente polinómico si:
Cualquier algoritmo con estas dos propiedades se puede convertir en un algoritmo de tiempo polinómico reemplazando las operaciones aritméticas por algoritmos adecuados para realizar las operaciones aritméticas en una máquina de Turing . Si el segundo de los requisitos anteriores no se cumple, entonces esto ya no es cierto. Dado el entero (que ocupa un espacio proporcional a n en el modelo de máquina de Turing), es posible calcular con n multiplicaciones usando exponenciación binaria. Sin embargo, el espacio utilizado para representar es proporcional a y, por lo tanto, exponencial en lugar de polinomico en el espacio utilizado para representar la entrada. Por lo tanto, no es posible llevar a cabo este cálculo en tiempo polinómico en una máquina de Turing pero es posible calcularlo polinómicamente con muchas operaciones aritméticas.
Por el contrario, existen algoritmos que se ejecutan en varios pasos de la máquina de Turing delimitados por un polinomio en la longitud de la entrada codificada en binario pero no toman una serie de operaciones aritméticas delimitadas por un polinomio en el número de números de entrada. El algoritmo euclidiano para calcular el máximo divisor común de dos enteros es un ejemplo. Dados dos enteros y , el algoritmo realiza operaciones aritméticas en números con como máximo bits. Al mismo tiempo, el número de operaciones aritméticas no puede estar limitado por el número de enteros en la entrada (que es constante en este caso, siempre hay solo dos enteros en la entrada). Debido a la última observación, el algoritmo no se ejecuta en un tiempo fuertemente polinómico. Su tiempo real de ejecución depende de las magnitudes de y y no solo en el número de enteros en la entrada.
Se dice que un algoritmo que se ejecuta en tiempo polinomial pero que no es fuertemente polinomial se ejecuta en tiempo polinomial débil. Un ejemplo bien conocido de un problema para el que se conoce un algoritmo de tiempo polinomial débil, pero no se sabe que admita un algoritmo de tiempo polinomial fuerte, es la programación lineal. El tiempo débilmente polinomial no debe confundirse con el tiempo pseudopolinómico.
El concepto de tiempo polinomial conduce a varias clases de complejidad en la teoría de la complejidad computacional. Algunas clases importantes definidas usando el tiempo polinomial son las siguientes.
P es la clase de complejidad temporal más pequeña en una máquina determinista que es robusta en términos de cambios en el modelo de máquina. (Por ejemplo, un cambio de una máquina de Turing de una sola cinta a una máquina de varias cintas puede conducir a una aceleración cuadrática pero cualquier algoritmo que se ejecute en tiempo polinómico en un modelo también lo hace en el otro). Cualquier máquina abstracta tendrá una clase de complejidad correspondiente a los problemas que se pueden resolver en tiempo polinómico en esa máquina.
Se dice que un algoritmo toma tiempo superpolinomial si T (n) no está limitado por ningún polinomio. Usando una notación omega chica, es el tiempo ω(nc) para todas las constantes c, donde n es el parámetro de entrada, típicamente el número de bits en la entrada.
Por ejemplo, un algoritmo que se ejecuta durante 2n pasos en una entrada de tamaño n requiere tiempo superpolinomial (más específicamente, tiempo exponencial).
Un algoritmo que utiliza recursos exponenciales es claramente superpolinomial, pero algunos algoritmos son muy débilmente superpolinomiales. Por ejemplo, la prueba de primalidad Adleman – Pomerance – Rumely se ejecuta durante nO(log log n) en entradas de n bits; esto crece más rápido que cualquier polinomio para una n lo suficientemente grande pero el tamaño de entrada debe hacerse tan grande como para volverse impráctico si se quiere evitar ser dominado por un polinomio de pequeño grado.
Un algoritmo que requiere tiempo superpolinomial se encuentra fuera de la clase de complejidad P. La tesis de Cobham postula que estos algoritmos no son prácticos. Dado que el problema P versus NP no está resuelto, actualmente no se sabe de un algoritmo para un problema NP completo que se ejecute en tiempo polinómico.
Los algoritmos de tiempo cuasi polinomiales son algoritmos que funcionan más lentamente que aquellos de tiempo polinómico pero no tan lentos como para ser de tiempo exponencial. El peor tiempo de ejecución de un algoritmo de tiempo cuasi polinomial es para una constante . Para obtenemos un algoritmo de tiempo polinómico, para obtenemos un algoritmo de tiempo sub-lineal.
Los algoritmos de tiempo cuasi polinomiales generalmente surgen en reducciones de un problema NP-hard a otro problema. Por ejemplo, uno puede tomar una instancia de un problema NP-hard, digamos 3SAT, y convertirlo en una instancia de otro problema B, pero el tamaño de la instancia se convierte en . En ese caso, esta reducción no prueba que el problema B sea NP-hard; esta reducción solo muestra que no existe un algoritmo de tiempo polinómico para B a menos que exista un algoritmo de tiempo cuasi polinómico para 3SAT (y, por lo tanto, todo NP). De manera similar, existen algunos problemas para los cuales conocemos algoritmos de tiempo cuasi-polinomiales pero no de tiempo polinomial. Tales problemas surgen en los algoritmos de aproximación; Un ejemplo famoso es el problema del árbol Steiner dirigido, para el cual existe un algoritmo de aproximación de tiempo cuasi polinomial que logra un factor de aproximación de (n es el número de vértices), pero la demostración de la existencia de dicho algoritmo de tiempo polinomial es un problema abierto.
Otros problemas computacionales con soluciones de tiempo cuasi-polinomiales pero ninguna solución de tiempo polinomial conocida incluye el problema de planted cliques en el que el objetivo es encontrar un clique mayor en la unión de una clique y un grafo aleatorio. Aunque cuasi-polinomialmente solucionable, se ha conjeturado que el problema de planted cliques no tiene una solución de tiempo polinomial; Esta conjetura se ha utilizado como un supuesto de dureza computacional para demostrar la dificultad de varios otros problemas en la teoría de juegos computacionales, property testing y el aprendizaje automático.
La clase de complejidad QP consiste en todos los problemas que tienen algoritmos de tiempo cuasi-polinomiales. Se puede definir en términos de DTIME de la siguiente manera:
En teoría de la complejidad, el problema de P versus NP sin resolver pregunta si todos los problemas en NP tienen algoritmos de tiempo polinomial. Todos los algoritmos más conocidos para problemas NP-completos como 3SAT, etc. toman tiempo exponencial. De hecho, se conjetura para muchos problemas naturales completos de NP que no tienen algoritmos de tiempo sub-exponenciales. Aquí "tiempo sub-exponencial" se entiende como la segunda definición presentada a continuación. (Por otro lado, muchos problemas de grafos representados de forma natural por matrices de adyacencia se pueden resolver en tiempo subexponencial simplemente porque el tamaño de la entrada es el cuadrado del número de vértices.) Esta conjetura (para el problema k-SAT) se conoce como la hipótesis del tiempo exponencial. Dado que se conjetura que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales, algunos resultados de inaplicabilidad en el campo de los algoritmos de aproximación suponen que los problemas NP-completos no tienen algoritmos de tiempo cuasi-polinomiales. Por ejemplo, vea los resultados de inaplicabilidad conocidos para el problema de la cobertura de conjuntos.
El término tiempo sub-exponencial se usa para expresar que el tiempo de ejecución de algún algoritmo puede crecer más rápido que cualquier polinomio pero aún es significativamente más pequeño que un exponencial. En este sentido, los problemas que tienen algoritmos de tiempo sub-exponenciales son algo más manejables que aquellos que solo tienen algoritmos exponenciales. Generalmente no hay consenso respecto a la definición precisa de "sub-exponencial", enumeramos las dos más utilizados a continuación:
Se dice que un problema puede resolverse con un tiempo sub-exponencial si se puede resolver en tiempos de ejecución cuyos logaritmos crecen más lentamente que cualquier polinomio dado. Más precisamente, un problema toma un tiempo sub-exponencial si por cada ε>0 existe un algoritmo que resuelve el problema en el tiempo O (2nε). El conjunto de todos estos problemas es la clase de complejidad SUBEXP que se puede definir en términos de DTIME de la siguiente manera:
Esta noción de sub-exponencial no es uniforme en términos de ε en el sentido de que ε no es parte de la entrada y cada ε puede tener su propio algoritmo para el problema.
Algunos autores definen el tiempo sub-exponencial como tiempos de ejecución en 2o(n). Esta definición permite tiempos de ejecución mayores que la primera definición de tiempo sub-exponencial. Un ejemplo de dicho algoritmo de tiempo sub-exponencial es el algoritmo clásico más conocido para la factorización de enteros, la criba general del cuerpo de números , que se ejecuta en un tiempo de , donde n es la longitud de la entrada. Otro ejemplo es el problema del isomorfismo de grafos, donde el algoritmo de Luks se ejecuta a tiempo . (En 2015–2017, Babai redujo la complejidad de este problema al tiempo cuasi polinomial.)
Si el algoritmo puede ser sub-exponencial en el tamaño de la instancia, el número de vértices o el número de aristas, eso hace una diferencia. En la complejidad parametrizada, esta diferencia se hace explícita considerando pares de problemas de decisión y parámetros k. SUBEPT es la clase de todos los problemas parametrizados que se ejecutan en tiempo sub-exponencial en k y en tiempo polinomico en el tamaño de entrada n:
Más precisamente, SUBEPT es la clase de todos los problemas parametrizados para los cuáles hay una función computable con y un algoritmo que decide L en tiempo .
La hipótesis del tiempo exponencial (ETH ) es que 3SAT, el problema de satisfacción de las fórmulas booleanas en forma conjuntiva normal con, como máximo, tres literales por cláusula y con n variables, no puede resolverse en el tiempo 2o(n) . Más precisamente, la hipótesis es que existe una constante absoluta c>0 tal que 3SAT no puede decidirse en tiempo 2cn por ninguna máquina determinista de Turing. Con m denotando el número de cláusulas, ETH es equivalente a la hipótesis de que k-SAT no puede resolverse en el tiempo 2o(m) para cualquier entero k ≥ 3 La hipótesis del tiempo exponencial implica P ≠ NP .
Se dice que un algoritmo es de tiempo exponencial, si T(n) está limitado por 2poly(n), donde poly(n) es un polinomio en n. Más formalmente, un algoritmo es de tiempo exponencial si T(n) está limitado por O(2nk) para alguna constante k. Los problemas que admiten algoritmos de tiempo exponencial en una máquina de Turing determinista forman la clase de complejidad conocida como EXP.
A veces, el tiempo exponencial se usa para referirse a algoritmos que tienen T(n) = 2O(n), donde el exponente es como máximo una función lineal de n. Esto da lugar a la clase de complejidad E.
Un ejemplo de un algoritmo que se ejecuta en tiempo factorial es bogosort, un algoritmo de clasificación notoriamente ineficiente basado en prueba y error. Bogosort ordena una lista de n elementos mezclando repetidamente la lista hasta que se encuentre ordenada. En el caso promedio, cada paso a través del algoritmo bogosort examinará uno de los n! ordenamientos de los n elementos. Si los elementos son distintos, solo se ordena uno de esos pedidos. Bogosort comparte patrimonio con el teorema del mono infinito .
Se dice que un algoritmo es el tiempo exponencial doble si T (n) está limitado por 22poli (n), donde poly (n) es algún polinomio en n. Dichos algoritmos pertenecen a la clase de complejidad 2-EXPTIME .
Los algoritmos de tiempo doble exponencial bien conocidos incluyen: