Ver el código de «Complejidad temporal»

[[Archivo:Comparison_computational_complexity.svg|miniaturadeimagen| Gráficos de funciones comúnmente utilizadas en el [[análisis de algoritmos]], que muestran el número de operaciones ''N'' versus el tamaño de entrada ''n'' para cada función ]]
En [[Ciencias de la computación|informática]], la '''complejidad''' '''temporal''' es la [[complejidad de algoritmo|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 [[Cota superior asintótica|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 matemática|función]] del tamaño de la entrada.<ref name="Sipser">{{Cita libro|apellidos=Sipser|nombre=Michael|enlaceautor=Michael Sipser|título=Introduction to the Theory of Computation|año=2006|editorial=Course Technology Inc|isbn=0-619-21764-2}}</ref> 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 [[Análisis asintótico|comportamiento asintótico]] de la complejidad. Por lo tanto, la complejidad temporal se expresa comúnmente usando [[Cota superior asintótica|la notación O grande]], típicamente {{nowrap|<math>O(n)</math>,}} {{nowrap|<math>O(n\log n)</math>,}} {{nowrap|<math>O(n^\alpha)</math>,}} {{nowrap|<math>O(2^n)</math>,}} etc., donde {{Mvar|n}} es el tamaño de entrada en unidades de [[Bit|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 <math>O(n)</math> es un ''algoritmo de tiempo lineal'' y un algoritmo con complejidad de tiempo <math>O(n^\alpha)</math> por alguna constante <math>\alpha > 1</math> es un ''algoritmo de tiempo polinómico'' . 

== Tabla de complejidades temporales comunes ==
La siguiente tabla resume algunas clases de complejidades de tiempo comúnmente encontradas. En la tabla, poly(''x'') = ''x''<sup>''O''(1)</sup>, es decir, polinomial en ''x'' . 
{| class="wikitable sortable"
!Nombre
!Clase de complejidad
!Tiempo de ejecución (''T''(''n''))
!Ejemplos de tiempo de ejecución
!Algoritmos de ejemplo
|-
|Tiempo constante
|
|''O''(1)
|10
|Encontrar la mediana en un [[Vector (informática)|array]] ordenado de números.
|-
|Tiempo inverso de la [[función de Ackermann]]
|
|''O''(''α''(''n''))
|
|[[Análisis de amortización|Tiempo amortizado]]  por operación usando un [[Estructura de datos para conjuntos disjuntos|conjunto disjunto]] 
|-
|Tiempo de
[[logaritmo iterado]]
|
|''O''(''log*n'')
|
|[[Coloración de grafos|Coloración distribuida de grafos]]
|-
|Log-logaritmico
|
|''O''(log log ''n'')
|
|Tiempo amortizado por operación usando una [[cola de prioridades]]<ref>{{Cita publicación|título=Bounded ordered dictionaries in O(log log N) time and O(n) space|apellidos=Mehlhorn|nombre=Kurt|apellidos2=Naher|nombre2=Stefan|publicación=Information Processing Letters|volumen=35|número=4|páginas=183–189|doi=10.1016/0020-0190(90)90022-P|año=1990}}</ref> acotada.
|-
|Tiempo logarítimico
|[[DLOGTIME]]
|''O''(log&nbsp;''n'')
|log&nbsp;''n'', log(''n''<sup>2</sup>)
|[[Búsqueda binaria]]
|-
|Tiempo polilogarítmico
|
|poly(log&nbsp;''n'')
|(log&nbsp;''n'')<sup>2</sup>
|
|-
|Poder fraccional
|
|{{Math|''O''(''n''<sup>c</sup>)}} donde {{Math|0 < c < 1}}
|''n''<sup>1/2</sup>, ''n''<sup>2/3</sup>
|Buscando en un [[árbol kd]]
|-
|Tiempo lineal
|
|''O''(''n'')
|''n'', ''2n + 5''
|Encontrar el item más grande o más pequeño en un [[Vector (informática)|array]] desordenado. [[ Algoritmo de Kadane |Kadane's algorithm]]
|-
|Tiempo "n log-estrella n" 
|
|''O''(''n''&nbsp;log*&nbsp;''n'')
|
|Algoritmo de [[Triangulación de un polígono|triangulación de polígonos]] de [[Raimund Seidel|Seidel]]
|-
|Tiempo linealitmico
|
|''O''(''n''&nbsp;log&nbsp;''n'')
|''n''&nbsp;log&nbsp;''n'', log ''n''!
|El ordenamiento por comparación más rápido posible; [[Transformada rápida de Fourier]]
|-
|Tiempo cuasilineal
|
|''n''&nbsp;poly(log&nbsp;''n'')
|
|
|-
|Tiempo cuadrático
|
|''O''(''n''<sup>2</sup>)
|''n''<sup>2</sup>
|[[Ordenamiento de burbuja|''Bubble sort'']]; [[Ordenamiento por inserción|''Insertion sort'']]; [[Teorema de convolución|Convolución directa]]
|-
|Tiempo cúbico
|
|''O''(''n''<sup>3</sup>)
|''n''<sup>3</sup>
|Multiplicación ingenua de dos matrices de ''n''×''n''. Cálculo de[[correlación parcial]].
|-
|Tiempo polinómico
|[[P (clase de complejidad)|P]]
|2<sup>''O''(log&nbsp;''n'')</sup> = poly(''n'')
|''n''{{Exp|2}} + ''n'', ''n''<sup>10</sup>
|Algoritmo de Karmarkar para [[programación lineal]]; [[Test de primalidad AKS]]<ref name="tao-aks">{{Cita libro|título=An epsilon of room, II: Pages from year three of a mathematical blog|apellidos=Tao|nombre=Terence|editorial=American Mathematical Society|año=2010|isbn=978-0-8218-5280-4|serie=Graduate Studies in Mathematics|volumen=117|ubicación=Providence, RI|páginas=82–86|capítulo=1.11 The AKS primality test|doi=10.1090/gsm/117|enlaceautor=Terence Tao}}</ref><ref>{{Cita publicación|url=https://math.dartmouth.edu/~carlp/aks111216.pdf|título=Primality testing with Gaussian periods|apellidos=Lenstra|nombre=Jr., H.W.|enlaceautor=Hendrik Lenstra|apellidos2=Pomerance|nombre2=Carl|enlaceautor2=Carl Pomerance|fecha=11 de diciembre de 2016}}</ref>
|-
|Tiempo cuasipolinomial
|QP
|2<sup>poly(log&nbsp;''n'')</sup>
|''n''<sup>log&nbsp;log&nbsp;''n''</sup>, ''n''<sup>log&nbsp;''n''</sup>
|O(log<sup>2</sup> ''n''), mejor[[Algoritmo de aproximación|algoritmo conocido de aproximación]] para el [[Árbol de Steiner|el problema del árbol de Steiner]] directo
|-
|Tiempo sub-exponencial<br /><br />(primera definición)
|SUBEXP
|''O''(2<sup>''n''<sup>''ε''</sup></sup>) para todo ''ε''&nbsp;>&nbsp;0
|''O''(2<sup>log ''n''<sup>log log ''n''</sup></sup>)
|
|-
|Tiempo sub-exponencial<br /><br />(segunda definición)
|
|2<sup>''o''(''n'')</sup>
|2<sup>''n''<sup>1/3</sup></sup>
|[[Criba general del cuerpo de números|Mejor algoritmo conocido para]] for [[factorización de enteros]]; anteriormente el mejor algoritmo para [[Problema del isomorfismo de grafos|el problema del isomorfismo de grafos]]
|-
|Tiempo exponencial<br />(con exponente lineal)
|[[E (clase de complejidad)|E]]
|2<sup>''O''(''n'')</sup>
|1.1<sup>''n''</sup>, 10<sup>''n''</sup>
|Resolución del [[problema del viajante]]  usando [[programación dinámica]]
|-
|Tiempo exponencial
|[[EXPTIME]]
|2<sup>poly(''n'')</sup>
|2<sup>''n''</sup>, 2<sup>''n''<sup>2</sup></sup>
|Resolución de multiplicación de matrices encadenadas via [[Búsqueda de fuerza bruta|brute-force search]]
|-
|Tiempo factorial
|
|''O''(''n''!)
|''n''!
|Resolviendo el [[Problema del viajante|problema del viajero]] usando [[búsqueda de fuerza bruta]]
|-
|Tiempo exponencial doble
|2-EXPTIME
|2<sup>2<sup>poly(''n'')</sup></sup>
|2<sup>2<sup>''n''</sup></sup>
|Deciding the truth of a given statement in [[ Aritmética pre hamburguesa |Aritmética de Presburguer]]
|}

== Tiempo constante ==
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 [[Vector (informática)|matriz]] requiere tiempo constante, ya que solo se debe realizar una [[Conjunto de instrucciones|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 un conjunto|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.   : 
 int index = 5;
 int item = lista[index];
 '''if''' (condición verdadera) '''then'''
   realizar alguna operación que se ejecuta en tiempo constante
 '''else'''
   realizar alguna otra operación que se ejecute en tiempo constante
 '''for''' i=1 '''to''' 100
   for j=1 '''to''' 200
    realizar alguna operación que se ejecuta en tiempo constante 
Si ''T''(''n'') es O(''cualquier valor constante'') se indica en notación estándar como ''T''(''n'') siendo O(1). 

== Tiempo logarítmico ==
Se dice que un algoritmo toma '''tiempo logarítmico''' cuando ''T''(''n'') = '''O(log ''n'')''' . Dado que log <sub>a</sub> ''n'' y log <sub>b</sub> ''n'' están relacionados por un [[Identidades logarítmicas|multiplicador constante]], y dicho [[Cota superior asintótica|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 [[Árbol binario|á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]] {{Math|''D''}} que contiene ''n'' entradas, ordenadas por [[orden alfabético]]. Suponemos que, para {{Math|1 ≤ ''k'' ≤ ''n''}}, uno puede acceder a la entrada {{Mvar|k}} del diccionario en un tiempo constante. Usemos {{Math|''D''(''k'')}} para denotar la {{Mvar|k}}-ésima entrada. Bajo estas hipótesis, la prueba de si una palabra {{Mvar|''w''}} está en el diccionario se puede hacer en tiempo logarítmico: considere <math>D(\lfloor n/2 \rfloor),</math> dónde <math>\lfloor\;\rfloor</math> denota la [[Funciones de parte entera|función de piso]] . Si <math>w=D(\lfloor n/2 \rfloor),</math> entonces hemos terminado. Si no <math>w<D(\lfloor n/2 \rfloor),</math> 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. 

== Tiempo poli-logarítmico ==
Se dice que un algoritmo se ejecuta en '''tiempo poli-logarítmico''' si ''T''(''n'') = O ((log ''n'' )<sup>''k''</sup> ), 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]].<ref>{{Cita publicación|título=Efficient Matrix Chain Ordering in Polylog Time|apellidos=Bradford|nombre=Phillip G.|apellidos2=Rawlins|nombre2=Gregory J. E.|publicación=SIAM Journal on Computing|editorial=[[Society for Industrial and Applied Mathematics]]|volumen=27|número=2|páginas=466–490|ubicación=Philadelphia|issn=1095-7111|doi=10.1137/S0097539794270698|apellidos3=Shannon|nombre3=Gregory E.|año=1998}}</ref> 

== Tiempo sub-lineal ==
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 [[Algoritmo paralelo|procesamiento paralelo]] (como lo hace el cálculo del determinante de una matriz NC<sub>1</sub>), o alternativamente tienen suposiciones garantizadas en la estructura de entrada (como lo hacen la [[Búsqueda binaria|búsqueda binaria de]] tiempo logarítmico y muchos algoritmos de mantenimiento de árboles). Sin embargo, [[Lenguaje formal|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.<ref>{{Cita publicación|url=http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/kumarR-survey.pdf|título=Sublinear time algorithms|apellidos=Kumar|nombre=Ravi|apellidos2=Rubinfeld|nombre2=Ronitt|publicación=SIGACT News|volumen=34|número=4|páginas=57–67|doi=10.1145/954092.954103|año=2003}}</ref> Sin embargo, se les permite ser [[Algoritmo probabilista|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 ''b''<sub>1</sub>,..., ''b<sub>k</sub>'' se supone que el algoritmo puede solicitar y obtener el valor de ''b<sub>i</sub>'' para cualquier ''i'' en tiempo O(1). 

Los algoritmos de tiempo sub-lineal suelen ser aleatorios y solo proporcionan soluciones [[Algoritmo de aproximación|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'' . 

== Tiempo lineal ==
Se dice que un algoritmo toma '''tiempo lineal''', o '''tiempo''' {{Math|''O''(''n'')}}, si su complejidad temporal es {{Math|''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 {{Mvar|c}} tal que el tiempo de ejecución es como máximo {{Math|''cn''}} para cada entrada de tamaño {{Mvar|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 [[Computación paralela|paralelismo]] para proporcionar esto. Un ejemplo es la [[Memoria de contenido direccionable|memoria direccionable por contenido]] . Este concepto de tiempo lineal se utiliza en algoritmos de coincidencia de cadenas como el algoritmo de [[Algoritmo de búsqueda de cadenas Boyer-Moore|Boyer-Moore]] y [[Algoritmo de Ukkonen|el algoritmo de Ukkonen]] . 

== Tiempo cuasilineal ==
Se dice que un algoritmo se ejecuta en '''tiempo cuasilineal''' (también denominado '''tiempo''' '''log-lineal''') si ''T'' (''n'')='''O(''n'' log <sup>''k''</sup> ''n'')''' para alguna constante positiva ''k'';<ref>{{Cita publicación|url=http://www.cse.buffalo.edu/~regan/papers/pdf/NRS95.pdf|título=On Quasilinear Time Complexity Theory|apellidos=Naik|nombre=Ashish V.|apellidos2=Regan|nombre2=Kenneth W.|fecha=1995|publicación=Theoretical Computer Science|volumen=148|número=2|páginas=325–349|fechaacceso=23 de febrero de 2015|doi=10.1016/0304-3975(95)00031-q|apellidos3=Sivakumar|nombre3=D.}}</ref> el caso de ''k''=1 se llama '''tiempo linealitmico'''.<ref>Sedgewick, R. and Wayne K (2011). [http://algs4.cs.princeton.edu/home/ Algorithms, 4th Ed]. p. 186. Pearson Education, Inc.</ref> Usando [[Cota superior asintótica|la notación O suave,]] estos algoritmos son Õ(''n''). Los algoritmos de tiempo cuasilineal también son O(''n''<sup>1+ε</sup>) 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 ''n''<sup>''c''</sup> para cualquier ''c''>1) 

Los algoritmos que se ejecutan en tiempo cuasilineal incluyen: 

* [[Ordenamiento por mezcla|Merge sort in-place]], O(''n'' log<sup>''2''</sup> ''n'') 
* [[Quicksort]], O(''n'' log ''n''), en su versión aleatoria, tiene un tiempo de ejecución que es O(''n'' log ''n'') en espera de la entrada del peor de los casos. Su versión no aleatoria tiene un tiempo de ejecución O(''n'' log ''n'') solo cuando se considera la complejidad promedio de los casos. 
* [[Heapsort]], O(''n'' log ''n''), [[Ordenamiento por mezcla|merge sort]], [[introsort]], binary tree sort, [[smoothsort]], patience sorting, etc. en el peor de los casos 
* [[Transformada rápida de Fourier|Transformadas rápidas de Fourier]], O (''n'' log ''n'') 
* Cálculo de [[ Monge array |matriz Monge]], O (''n'' log ''n'') 

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 con árbol binario|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 binario de búsqueda auto-balanceable|á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 [[Fórmula de Stirling|aproximación de Stirling]]. Esto tiempos también surgen con frecuencia de la [[relación de recurrencia]] ''T''(''n'') = 2''T''(''n''/2) + ''O'' (''n''). 

== Tiempo sub-cuadrático ==
Se dice que un [[algoritmo]] es de '''tiempo subcuadrático''' si ''T'' (''n'') = O(''n''<sup>2</sup>). 

Por ejemplo, [[Algoritmo de ordenamiento|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|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. 

== Tiempo polinomial ==
Se dice que un algoritmo es de '''tiempo polinómico''' si su tiempo de ejecución está [[Elemento mayorante y minorante|limitado]] por una [[Anillo de polinomios|expresión polinómica]] en el tamaño de la entrada para el algoritmo, es decir, ''T'' (''n'') = O(''n''<sup>''k''</sup>) para alguna constante positiva ''k''.<ref name="Sipser"/><ref>{{Cita libro|apellidos=Papadimitriou|nombre=Christos H.|enlaceautor=Christos H. Papadimitriou|título=Computational complexity|url=https://archive.org/details/computationalcom0000papa|año=1994|editorial=Addison-Wesley|ubicación=Reading, Mass.|isbn=0-201-53082-1}}</ref> [[Problema de decisión|Los problemas]] para los que existe un algoritmo de tiempo polinómico determinista pertenecen a la [[clase de complejidad]] '''[[P (clase de complejidad)|P]]''', que es central en el campo de [[Teoría de la complejidad computacional|la teoría de la complejidad computacional]]. [[ Tesis de Cobham |La tesis de Cobham]] establece que el tiempo polinomial es sinónimo de "manejable", "factible", "eficiente" o "rápido".<ref>{{Cita libro|apellidos=Cobham|nombre=Alan|enlaceautor=Alan Cobham|año=1965|capítulo=The intrinsic computational difficulty of functions|título=Proc. Logic, Methodology, and Philosophy of Science II|editorial=North Holland}}</ref> 

Algunos ejemplos de algoritmos de tiempo polinomiales: 

* El [[ordenamiento por selección]], para ''n'' enteros realiza <math>An^2</math> operaciones para alguna constante ''A.'' Por lo tanto, corre en el tiempo <math>O(n^2)</math> y es un algoritmo de tiempo polinómico. 
* Todas las operaciones aritméticas básicas (suma, resta, multiplicación, división y comparación) se pueden realizar en tiempo polinómico. 
* Las coincidencias máximas en los [[Grafo|grafos]] se pueden encontrar en el tiempo polinómico. 

=== Tiempo polinomial fuerte y débil ===
En algunos contextos, especialmente en la [[Optimización (matemática)|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:<ref>{{Cita libro|apellidos=Grötschel|nombre=Martin|enlaceautor=Martin Grötschel|apellidos2=László Lovász|enlaceautor3=Alexander Schrijver|apellidos3=Alexander Schrijver|año=1988|capítulo=Complexity, Oracles, and Numerical Computation|título=Geometric Algorithms and Combinatorial Optimization|editorial=Springer|isbn=0-387-13624-X|enlaceautor2=László Lovász}}</ref> 

# El número de operaciones en el modelo aritmético de computación está limitado por un polinomio en el número de enteros en la instancia de entrada; y 
# El espacio utilizado por el algoritmo está limitado por un polinomio en el tamaño de la entrada. 

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 <math>2^n</math> (que ocupa un espacio proporcional a ''n'' en el modelo de máquina de Turing), es posible calcular <math>2^{2^n}</math> con ''n'' multiplicaciones usando [[exponenciación binaria]]. Sin embargo, el espacio utilizado para representar <math>2^{2^n}</math> es proporcional a <math>2^n</math> 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 de Euclides|algoritmo euclidiano]] para calcular el [[Máximo común divisor|máximo divisor común]] de dos enteros es un ejemplo. Dados dos enteros <math>a</math> y <math>b</math>, el algoritmo realiza <math>O(\log\ a + \log\ b)</math> operaciones aritméticas en números con como máximo <math>O(\log\ a + \log\ b)</math> 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 <math>a</math> y <math>b</math> 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'''.<ref>{{Cita libro|apellidos=Schrijver|nombre=Alexander|enlaceautor=Alexander Schrijver|año=2003|capítulo=Preliminaries on algorithms and Complexity|título=Combinatorial Optimization: Polyhedra and Efficiency|volumen=1|editorial=Springer|isbn=3-540-44389-4}}</ref> 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 [[Programación lineal|la programación lineal]]. El tiempo débilmente polinomial no debe confundirse con el tiempo [[Tiempo pseudo-polinómico|pseudopolinómico]]. 

=== Clases de complejidad ===
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. 
{| class="wikitable"
| '''[[P (clase de complejidad)|P]]''' 
| La [[Clase de complejidad|clase]] de [[Clase de complejidad|complejidad]] de [[Problema de decisión|los problemas]] de [[Problema de decisión|decisión]] que se pueden resolver en una [[Máquina de Turing|máquina de Turing determinista]] en tiempo polinómico 
|-
| '''NP''' 
| La clase de complejidad de los problemas de decisión que se pueden resolver en una [[máquina de Turing no determinista]] en tiempo polinómico 
|-
| '''[[ ZPP (complejidad) |ZPP]]''' 
| La clase de complejidad de los problemas de decisión que se pueden resolver con cero errores en una [[máquina de Turing probabilística]] en tiempo polinómico 
|-
| '''[[ RP (complejidad) |RP]]''' 
| La clase de complejidad de los problemas de decisión que se pueden resolver con un error unilateral en una máquina de Turing probabilística en tiempo polinómico. 
|-
| '''[[ BPP (complejidad) |BPP]]''' 
| La clase de complejidad de los problemas de decisión que se pueden resolver con un error de 2 lados en una máquina de Turing probabilística en tiempo polinómico 
|-
| '''[[BQP]]''' 
| La clase de complejidad de los problemas de decisión que se pueden resolver con un error de 2 lados en una [[máquina cuántica de Turing]] en tiempo polinómico 
|}
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. 

== Tiempo superpolinomial ==
Se dice que un algoritmo toma '''tiempo superpolinomial''' si ''T'' (''n'') no está limitado por ningún polinomio. Usando una [[Cota superior asintótica|notación omega chica]], es el tiempo ω(''n''<sup>''c''</sup>) 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 2<sup>''n''</sup> 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 de Adleman-Pomerance-Rumely |prueba de primalidad Adleman – Pomerance – Rumely]] se ejecuta durante ''n''<sup>O(log log ''n'')</sup> 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 (clase de complejidad)|P.]]''' [[ Tesis de Cobham |La tesis de Cobham]] postula que estos algoritmos no son prácticos. Dado que el [[Clases de complejidad P y NP|problema P versus NP]] no está resuelto, actualmente no se sabe de un algoritmo para un [[NP-completo|problema NP completo]] que se ejecute en tiempo polinómico. 

== Tiempo cuasi polinomial ==
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 <math>2^{O((\log n)^c)}</math> para una constante <math>c > 0</math>. Para <math>c=1</math> obtenemos un algoritmo de tiempo polinómico, para <math>c<1</math> obtenemos un algoritmo de tiempo sub-lineal. 

Los algoritmos de tiempo cuasi polinomiales generalmente surgen en [[Reducción (complejidad)|reducciones]] de un [[NP-hard|problema NP-hard]] a otro problema. Por ejemplo, uno puede tomar una instancia de un problema NP-hard, digamos [[Problema de satisfacibilidad booleana|3SAT]], y convertirlo en una instancia de otro problema B, pero el tamaño de la instancia se convierte en <math>2^{O((\log n)^c)}</math>. 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 (clase de complejidad)|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 [[Árbol de Steiner|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 <math>O(\log^3 n)</math> (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 [[Problema de la clique|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, [[ Prueba de propiedad |property testing]] y [[Aprendizaje automático|el aprendizaje automático]].<ref>{{Obra citada|título=ETH hardness for densest-{{mvar|k}}-subgraph with perfect completeness|apellidos=Braverman|nombre=Mark|apellidos2=Ko|nombre2=Young Kun|apellidos3=Rubinstein|nombre3=Aviad|apellidos4=Weinstein|nombre4=Omri|bibcode=2015arXiv150408352B|year=2015}}.</ref> 

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|DTIME de la]] siguiente manera:<ref>{{ComplexityZoo|Class QP: Quasipolynomial-Time|Q#qp}}</ref> 

: <math>\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}(2^{(\log n)^c})</math>

=== Relación con problemas NP-completos ===
En teoría de la complejidad, el problema de [[Clases de complejidad P y NP|P versus NP sin]] resolver pregunta si todos los problemas en NP tienen algoritmos de tiempo polinomial. Todos los algoritmos más conocidos para [[NP-completo|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 de tiempo exponencial |hipótesis del tiempo exponencial]].<ref name="ETH">{{Cita publicación|título=On the complexity of k-SAT|apellidos=Impagliazzo|nombre=R.|apellidos2=Paturi|nombre2=R.|publicación=Journal of Computer and System Sciences|editorial=[[Elsevier]]|volumen=62|número=2|páginas=367–375|issn=1090-2724|doi=10.1006/jcss.2000.1727|año=2001}}</ref> 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 [[Algoritmo de aproximación|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 [[Problema del conjunto de cobertura|cobertura de conjuntos]]. 

== Tiempo sub-exponencial ==
El término tiempo '''[[ Infra-exponencial |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",<ref>{{Cita web|url=http://scottaaronson.com/blog/?p=394|título=A not-quite-exponential dilemma|fechaacceso=2 de diciembre de 2009|autor=Aaronson, Scott|fecha=5 de abril de 2009|sitioweb=Shtetl-Optimized}}</ref> enumeramos las dos más utilizados a continuación: 

=== Primera definició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 (2<sup>n<sup>ε</sup></sup>). El conjunto de todos estos problemas es la clase de complejidad '''SUBEXP''' que se puede definir en términos de [[DTIME|DTIME de la]] siguiente manera:<ref name="bpp">{{Cita publicación|título=BPP has subexponential time simulations unless EXPTIME has publishable proofs|apellidos=Babai|nombre=László|enlaceautor=László Babai|apellidos2=Fortnow|nombre2=Lance|enlaceautor2=Lance Fortnow|publicación=Computational Complexity|editorial=[[Springer-Verlag]]|volumen=3|número=4|páginas=307–318|ubicación=Berlin, New York|doi=10.1007/BF01275486|apellidos3=Nisan|nombre3=N.|enlaceautor3=Noam Nisan|apellidos4=Wigderson|nombre4=Avi|enlaceautor4=Avi Wigderson|año=1993}}</ref><ref>{{ComplexityZoo|Class SUBEXP: Deterministic Subexponential-Time|S#subexp}}</ref><ref>{{Cita conferencia|título=Baire’s Categories on Small Complexity Classes|autor1=Philippe Moser|año=2003|volumen=2751|páginas=333–342|doi=10.1007/978-3-540-45077-1_31|isbn=978-3-540-40543-6}}</ref><ref>{{Cita publicación|título=Derandomizing Complexity Classes|apellidos=Miltersen|nombre=P.B.|publicación=Handbook of Randomized Computing|editorial=Kluwer Academic Pub|volumen=9|serie=Combinatorial Optimization|página=843|doi=10.1007/978-1-4615-0013-1_19|isbn=978-1-4613-4886-3|año=2001}}</ref> 

: <math>\text{SUBEXP}=\bigcap_{\varepsilon>0} \text{DTIME}\left(2^{n^\varepsilon}\right)</math>

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.

=== Segunda definición ===
Algunos autores definen el tiempo sub-exponencial como tiempos de ejecución en 2<sup>o(''n'')</sup>.<ref name="ETH"/><ref>{{Cita publicación|título=A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem|apellidos=Kuperberg|nombre=Greg|publicación=SIAM Journal on Computing|volumen=35|número=1|ubicación=Philadelphia|página=188|issn=1095-7111|doi=10.1137/s0097539703436345|año=2005|arxiv=quant-ph/0302112}}</ref><ref>{{Cita arXiv|arxiv=quant-ph/0406151v1|title=A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space|year=2004}}</ref> 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 <math>2^{\tilde{O}(n^{1/3})}</math>, 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 <math>2^{O(\sqrt{n \log n})}</math> . (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 <math>(L,k)</math> de [[Problema de decisión|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'':<ref>{{Cita libro|apellidos=Flum|nombre=Jörg|apellidos2=Grohe|nombre2=Martin|enlaceautor2=Martin Grohe|título=Parameterized Complexity Theory|año=2006|editorial=Springer|url=https://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0|isbn=978-3-540-29952-3|página=417|fechaacceso=14 de julio de 2020|fechaarchivo=18 de noviembre de 2007|urlarchivo=https://web.archive.org/web/20071118193434/http://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0|deadurl=yes}}</ref> 

: <math>\text{SUBEPT}=\text{DTIME}\left(2^{o(k)} \cdot \text{poly}(n)\right).</math>

Más precisamente, SUBEPT es la clase de todos los problemas parametrizados <math>(L,k)</math> para los cuáles hay una [[función computable]] <math>f : \mathbb N\to\mathbb N</math> con <math>f \in o(k)</math> y un algoritmo que decide ''L'' en tiempo <math>2^{f(k)} \cdot \text{poly}(n)</math> . 

==== Hipótesis de tiempo exponencial ====
La '''hipótesis del tiempo exponencial''' ('''ETH''' ) es que [[Problema de satisfacibilidad booleana|3SAT]], el problema de satisfacción de las fórmulas booleanas en forma [[Forma normal conjuntiva|conjuntiva normal]] con, como máximo, tres literales por cláusula y con ''n'' variables, no puede resolverse en el tiempo 2<sup>''o''(''n'')</sup> . Más precisamente, la hipótesis es que existe una constante absoluta {{Math|''c''>0}} tal que 3SAT no puede decidirse en tiempo 2<sup>''cn''</sup> 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 2<sup>''o''(''m'')</sup> para cualquier entero {{Math|''k''&nbsp;≥&nbsp;3}}<ref>{{Cita publicación|título=Which problems have strongly exponential complexity?|apellidos=Impagliazzo|nombre=R.|enlaceautor=Russell Impagliazzo|apellidos2=Paturi|nombre2=R.|publicación=[[Journal of Computer and System Sciences]]|volumen=63|número=4|páginas=512–530|doi=10.1006/jcss.2001.1774|apellidos3=Zane|nombre3=F.|año=2001}}</ref> La hipótesis del tiempo exponencial implica [[Clases de complejidad P y NP|P ≠ NP]] . 

== Tiempo exponencial ==
Se dice que un algoritmo es de '''tiempo exponencial''', si ''T''(''n'') está limitado por 2<sup>poly(''n'')</sup>, donde poly(''n'') es un polinomio en ''n''. Más formalmente, un algoritmo es de tiempo exponencial si ''T''(''n'') está limitado por O(2<sup>''n''<sup>''k''</sup></sup>) 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 '''[[EXPTIME|EXP]]'''. 

: <math>\text{EXP} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{n^c}\right)</math>

A veces, el tiempo exponencial se usa para referirse a algoritmos que tienen ''T''(''n'') = 2<sup>O(''n'')</sup>, donde el exponente es como máximo una función lineal de ''n''. Esto da lugar a la clase de complejidad '''[[E (clase de complejidad)|E.]]''' 

: <math>\text{E} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{cn}\right)</math>

== Tiempo factorial ==
Un ejemplo de un algoritmo que se ejecuta en tiempo factorial es [[Stupid sort|bogosort]], un algoritmo de clasificación notoriamente ineficiente basado en [[Ensayo y error|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]] . 

== Doble tiempo exponencial ==
Se dice que un algoritmo es el tiempo [[ Doble función exponencial |exponencial doble]] si ''T'' (''n'') está limitado por 2<sup>2<sup>poli (''n'')</sup></sup>, donde poly (''n'') es algún polinomio en ''n''. Dichos algoritmos pertenecen a la clase de complejidad [[2-EXPTIME]] . 

: <math>\mbox{2-EXPTIME} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}\left( 2^{2^{n^c}}\right)</math>

Los algoritmos de tiempo doble exponencial bien conocidos incluyen: 

* Procedimientos de decisión para [[ Aritmética pre hamburguesa |la aritmética de Presburger]] 
* Computación de una base de Gröbner (en el peor de los casos<ref>Mayr,E. & Mayer,A.: The Complexity of the Word Problem for Commutative Semi-groups and
Polynomial Ideals. ''Adv. in Math.'' 46(1982) pp. 305–329</ref>) 
* [[Eliminación de cuantificadores|La eliminación del cuantificador]] en [[ Campo cerrado real |campos cerrados reales]] requiere al menos un tiempo exponencial doble<ref>J.H. Davenport & J. Heintz: Real Quantifier Elimination is Doubly Exponential.
''J. Symbolic Comp.'' 5(1988) pp. 29–35.</ref><ref>G.E. Collins: Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic
Decomposition. Proc. 2nd. GI Conference Automata Theory & Formal Languages (Springer Lecture
Notes in Computer Science 33) pp. 134–183</ref> 

== Referencias ==
{{Listaref|33em}}

{{Control de autoridades}}
[[Categoría:Complejidad computacional]]
[[Categoría:Análisis de algoritmos]]
[[Categoría:Wikipedia:Páginas con traducciones sin revisar]]