Complejidad del tiempo
En ciencias de la computación , la complejidad del tiempo es la complejidad computacional que describe la cantidad de tiempo de computadora que se necesita para ejecutar un algoritmo . La complejidad del tiempo comúnmente se estima 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, la cantidad de tiempo empleado y el número de operaciones elementales realizadas por el algoritmo se consideran 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 del tiempo en el peor de los casos , que es la cantidad máxima de tiempo requerida para entradas de un tamaño determinado. Menos común, y por lo general se especifica explícitamente, es la complejidad del caso promedio , que es el promedio del tiempo que tardan 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 del tiempo generalmente se expresa en función del tamaño de la entrada. [1] : 226 Dado que esta función generalmente es difícil de calcular con exactitud, y el tiempo de ejecución para entradas pequeñas generalmente no tiene consecuencias, 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 del tiempo se expresa comúnmente usando la notación O grande , típicamente , , , , etc., donde n es el tamaño 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 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 de tiempo comúnmente encontradas. En la tabla, poly( x ) = x O (1) , es decir, polinomio en x .
Se dice que un algoritmo es de tiempo constante (también escrito como O (1) tiempo) si el valor de T ( n ) está acotado 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 localizarlo. 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.
