Análisis de Algoritmos

Por Stephan Aigneren

Qué es la complejidad dealgoritmos?

• Se dice que gira en torno a la complejidad de los problemas por solucionar.

• También mide la cantidad de recursos a utilizar, tanto espacio como tiempo, que el algoritmo necesite.

Espacio?

• Es la cantidad de memoria que se necesita para ejecutar el algoritmo.

• También está asociada a las estructuras de datos.

EJEMPLO

Tiempo?

Es la cantidad de segundos, minutos, etc. que necesita el algoritmo para ejecutar una operación.

Variables de entrada

• Cada algoritmo se comporta de manera diferente según como se le entregue la información.

• Es por ello por lo que hay que estudiar el comportamiento mirando hacia ambos extremos.

• ORDENADOS• DeSOrDenadoS

Complejidad del peor caso

Determina cuantas operaciones se deben hacer para que el algoritmo garantice una solución.

Complejidad del caso promedio

• Trata de buscar un “promedio de operaciones” realizadas para dar solución a un problema, considerando posibles “entradas” con un tamaño determinado.

Tiempo de Ejecución

• Es el interés principal para saber como y cuanto crece el tamaño de entrada. La función para medir la complejidad es la siguiente:

Que hace esta función

• Se puede medir físicamente ejecutando un programa.

• Calcularse sobre el código contando instrucciones a ejecutar multiplicado por el tiempo requerido por instrucción.

Notación asintótica

Se necesita analizar la capacidad del algoritmo independiente de la capacidad de la máquina.

Incluso la habilidad el programador que las codifique.

• Los problemas más pequeños tienen solución que se pueden resolver de cualquier forma.

• Sin embargo, nos interesa el análisis cuando el algoritmo es aplicado en problemas de grandes proporciones.

• Todo lo anterior nos lleva a estudiar el comportamiento de un algoritmo.

N INFINITO

(Comportamiento Asintótico)

Asintótico

• Analiza las funciones en base a su tasa de crecimiento.

• Se describe por medio de una función dominio es el número natural (N), a partir del tiempo de ejecución o espacio de memoria en base a la longitud de entrada.

• Big-O

El comportamiento asintótico identifica familia de funciones.

Si comparten un mismo comportamiento asintótico lo denominaremos “Orden de Complejidad”.

Estos conjuntos se denominan O.