¿Por qué la complejidad temporal no devuelve el tiempo de ejecución exacto de un algoritmo?

Mientras analizamos un algoritmo, seguimos el análisis APRIORI, en el que nuestro análisis es independiente del lenguaje de programación y del tipo de procesador. Y, por lo tanto, obtenemos la respuesta aproximada en lugar de la respuesta exacta.

ANÁLISIS APRIORI: – Es la determinación del orden de magnitud de una declaración.

ORDEN DE MAGNITUD DE UNA DECLARACIÓN: – Número de veces que la declaración se ejecutará mientras se ejecuta.

Nota: – Es por eso que durante el cálculo de la Complejidad de Tiempo de un Algoritmo, las constantes son ignoradas.

Porque no es un cálculo. Es una notación BIG OH aproximada. Sabes que te dice el límite superior del tiempo de ejecución de los algoritmos. Al igual que si hay un bucle que se ejecuta n / 2 veces, le dará aproximadamente O (n) complejidad de tiempo. Cuenta cientos de instrucciones de una sola línea como tiempo constante O (1). Entonces, aquí la complejidad del tiempo, especialmente Big Oh, no proporciona el tiempo de cálculo exacto, sino solo una aproximación del tiempo con respecto a la entrada. Para obtener más referencias, debe consultar el primer capítulo de Introducción a los algoritmos de CLRS.

Muchas rasones.

Primero, los algoritmos no tienen tiempo de ejecución: solo tienen complejidad. Las implementaciones tienen tiempo de ejecución. Es posible tener implementaciones eficientes e ineficientes del mismo algoritmo, que tendrán diferentes tiempos de ejecución dados los mismos datos de entrada.

En segundo lugar, la complejidad del tiempo solo relaciona el número de operaciones con el número de elementos de entrada. Esas operaciones pueden ser rápidas ( por ejemplo, comparaciones de clasificación) o lentas ( por ejemplo , movimientos de bloque o copias). Esto significa que la complejidad del tiempo no puede hacer predicciones sobre el tiempo transcurrido ejecutando una implementación de un algoritmo. Puede ver esto usted mismo realizando los pasos de clasificación rápida manualmente con una pila de naipes, y observando que realiza la tarea más lentamente que una computadora, mientras sigue el mismo algoritmo.

Tercero, muchos algoritmos no tienen una sola medida de complejidad temporal. La complejidad del tiempo depende en muchos casos de las características de entrada. Por esta razón, a menudo verá las complejidades de tiempo en el mejor de los casos, el peor de los casos y el caso promedio expresadas para un algoritmo. Un conjunto de datos de entrada particular puede caer en cualquier parte de ese continuo.