Complejidad de Algoritmos

   UNIVERSIDAD AUTÓNOMA DE QUERÉTARO[pic 1][pic 2]

        Facultad de Informática

        Algoritmos

Complejidad de algoritmos.

El análisis de algoritmos es una parte importante de la Teoría de Complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. 

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La Cota superior asintótica y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad.[pic 3]

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada, pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene ‘n’ elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de tiempo para devolver una respuesta.

El comportamiento de un algoritmo puede cambiar notablemente para diferentes entradas (lo ordenados que se encuentren y los datos a ordenar) Se Estudian tres casos:

• Caso peor: mayor número posible de instrucciones ejecutadas por el algoritmo.
• Caso mejor: menor número posible de instrucciones ejecutadas por el algoritmo.
• Caso medio: número de instrucciones igual a la esperanza matemática de la variable aleatoria definida por todas las posibles trazas del algoritmo para un tamaño de la entrada dado, con las probabilidades de que éstas ocurran para esa entrada.

Notación Asintóticas.

Las notaciones asintóticas son lenguajes que nos permitan analizar el tiempo de ejecución de un algoritmo identificando su comportamiento si el tamaño de entrada para el algoritmo aumenta. Esto también se conoce como la tasa de crecimiento de un algoritmo.

La notación asintótica nos permite representar la complejidad, y por ende la eficiencia, de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada (input).

La mayoría de los algoritmos están diseñados para trabajar con entradas de longitud arbitraria. El análisis de algoritmos es la determinación de la cantidad de recursos de tiempo y espacio necesarios para ejecutarlo. Por lo general, la eficiencia o el tiempo de ejecución de un algoritmo se establece como una función que relaciona la longitud de entrada con el número de pasos, conocido como complejidad de tiempo o volumen de memoria, conocido como complejidad de espacio.

La necesidad de analizar algoritmos surge como necesidad de eficiencia, es decir elegir un mejor algoritmo para un problema particular, ya que un problema computacional puede resolverse mediante diferentes algoritmos. Al considerar un algoritmo para un problema específico, podemos comenzar a desarrollar el reconocimiento de patrones de modo que la ayuda de este algoritmo pueda resolver tipos similares de problemas.

Los algoritmos a menudo son bastante diferentes entre sí, aunque el objetivo de estos algoritmos es el mismo. Por ejemplo, sabemos que un conjunto de números se puede ordenar usando diferentes algoritmos. El número de comparaciones realizadas por un algoritmo puede variar con otros para la misma entrada. Por lo tanto, la complejidad temporal de esos algoritmos puede diferir. Al mismo tiempo, necesitamos calcular el espacio de memoria requerido por cada algoritmo.

El análisis del algoritmo es el proceso de analizar la capacidad de resolución de problemas del algoritmo en términos del tiempo y el tamaño requeridos (el tamaño de la memoria para el almacenamiento durante la implementación). Sin embargo, la principal preocupación del análisis de algoritmos es el tiempo o rendimiento requerido.

...