Complejidad del tiempo
En ciencias de la computación , la complejidad del tiempo es la complejidad computacional que describe la cantidad de tiempo que lleva la computadora para ejecutar un algoritmo . La complejidad del tiempo 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 para realizarse. Por lo tanto, se considera que la cantidad de tiempo necesario y el número de operaciones elementales realizadas por el algoritmo están relacionados por un factor constante .
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 de tiempo del peor de los casos , que es la cantidad máxima de tiempo requerida para las entradas de un tamaño determinado. Menos común, y por lo general se especifica explícitamente, es la complejidad de caso promedio , que es el promedio del tiempo empleado en 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 del tiempo se expresa generalmente en función del tamaño de la entrada. [1] : 226 Dado que esta función es generalmente difícil de calcular con exactitud 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 la entrada, es decir, el comportamiento asintótico de la complejidad. Por lo tanto, la complejidad de tiempo se expresa comúnmente usando gran notación O , típicamente , , , , etc., donde n es el tamaño en unidades de bits de 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 de tiempo es un algoritmo de tiempo lineal y un algoritmo con complejidad de tiempo para alguna constante es un algoritmo de tiempo polinomial .
La siguiente tabla resume algunas clases de complejidades temporales que se encuentran comúnmente. En la tabla, poli ( x ) = x O (1) , es decir, polinomio en x .
Se dice que un algoritmo es tiempo constante (también escrito como O (1) tiempo) 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 lleva un tiempo constante ya que solo se debe realizar una operación para ubicarlo. De manera similar, encontrar el valor mínimo en una matriz ordenada en orden ascendente; es el primer elemento. Sin embargo, encontrar el valor mínimo en una matriz desordenada no es una operación de tiempo constante, ya que se necesita escanear cada elemento de la matriz para determinar el valor mínimo. Por lo tanto, es una operación de tiempo lineal, tomando O( n ) tiempo. Sin embargo, si el número de elementos se conoce de antemano y no cambia, se puede decir que dicho algoritmo se ejecuta en tiempo constante.
