Complejidad en el tiempo

Complejidad en el tiempo

Una medida que suele ser útil es conocer el tiempo de ejecución de un programa en función de N, lo cual se denomina T. Esta función se puede medir físicamente o se puede calcular sobre el código contando las instrucciones que se deben ejecutar y multiplicando el tiempo requerido por cada instrucción. Para ver los tiempos de un algoritmo se requiere un análisis a priori, y no a posteriori. En un análisis a priori se obtiene una función que acota el tiempo del algoritmo. En un análisis a posteriori se colecta una estadística sobre el desarrollo del algoritmo en tiempo y espacio al momento de su ejecución.

Cualquier fórmula T incluye referencias al parámetro N y a una serie de constantes K que dependen de factores externos al algoritmo, como pueden ser la calidad del código generado por el compilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta.

Esto, en principio, permite suponer que el problema se puede resolver n veces más rápido porque se tienen n procesadores. Desafortunadamente, este no es el caso, ya que existen diferentes conflictos, como el acceso a la memoria, el conflicto sobre la comunicación entre los trayectos de procesadores y procesadores a memoria, así como la ineficiencia por la implementación de la concurrencia de los algoritmos.  

Para cada procesador añadido, la velocidad es cada vez más lenta, lo que hace más complejo el manejo de los procesadores. Por esta razón, los esfuerzos van encaminados no solo a explotar la concurrencia en algoritmos, sino también a aprovechar de la mejor manera un número pequeño de procesadores veloces, en lugar de depender de más procesadores, lo cual disminuye la velocidad de ejecución. 

Para determinar la complejidad de un algoritmo es necesario analizar el comportamiento y ejecución de cada uno de sus pasos. Por ejemplo, ¿cuál es la complejidad del algoritmo 1.1

[pic 1]

...