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 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 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 .
Tabla de complejidades temporales comunes 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 . NombreClase de complejidadTiempo de ejecución (T(n))Ejemplos de tiempo de ejecuciónAlgoritmos de ejemploTiempo constanteO(1)10Encontrar la mediana en un array ordenado de números.Tiempo inverso de la función de AckermannO(α(n))Tiempo amortizado por operación usando un conjunto disjunto Tiempo de logaritmo iteradoO(log*n)Coloración distribuida de grafosLog-logaritmicoO(log log n)Tiempo amortizado por operación usando una cola de prioridades acotada.Tiempo logarítimicoDLOGTIMEO(log n)log n, log(n2)Búsqueda binariaTiempo polilogarítmicopoly(log n)(log n)2Poder fraccional donde n1/2, n2/3Buscando en un árbol kdTiempo linealO(n)n, 2n + 5Encontrar el item más grande o más pequeño en un array desordenado. Kadane's algorithmTiempo "n log-estrella n" O(n log* n)Algoritmo de triangulación de polígonos de SeidelTiempo linealitmicoO(n log n)n log n, log n!El ordenamiento por comparación más rápido posible; Transformada rápida de FourierTiempo cuasilinealn poly(log n)Tiempo cuadráticoO(n2)n2Bubble sort; Insertion sort; Convolución directaTiempo cúbicoO(n3)n3Multiplicación ingenua de dos matrices de n×n. Cálculo decorrelación parcial.Tiempo polinómicoP2O(log n) = poly(n)n + n, n10Algoritmo de Karmarkar para programación lineal; Test de primalidad AKSTiempo cuasipolinomialQP2poly(log n)nlog log n, nlog nO(log2 n), mejoralgoritmo conocido de aproximación para el el problema del árbol de Steiner directoTiempo sub-exponencial(primera definición)SUBEXPO(2nε) para todo ε > 0O(2log nlog log n)Tiempo sub-exponencial(segunda definición)2o(n)2n1/3Mejor algoritmo conocido para for factorización de enteros; anteriormente el mejor algoritmo para el problema del isomorfismo de grafosTiempo exponencial(con exponente lineal)E2O(n)1.1n, 10nResolución del problema del viajante usando programación dinámicaTiempo exponencialEXPTIME2poly(n)2n, 2n2Resolución de multiplicación de matrices encadenadas via brute-force searchTiempo factorialO(n!)n!Resolviendo el problema del viajero usando búsqueda de fuerza brutaTiempo exponencial doble2-EXPTIME22poly(n)22nDeciding the truth of a given statement in 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 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. : 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 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 que contiene n entradas, ordenadas por orden alfabético. Suponemos que, para , uno puede acceder a la entrada del diccionario en un tiempo constante. Usemos para denotar la -ésima entrada. Bajo estas hipótesis, la prueba de si una palabra 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.
Tiempo poli-logarítmico 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.
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 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 .
Tiempo lineal Se dice que un algoritmo toma tiempo lineal, o tiempo , si su complejidad temporal es . 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 tal que el tiempo de ejecución es como máximo para cada entrada de tamaño . 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 .
Tiempo cuasilineal