Análisis de Algoritmo

NombresPablo Rojas V.Asignatura: Análisis de AlgoritmoNombre del Profesor:Pilar PardoFecha:26 Marzo 2014

Complejidad de los algoritmos

• La complejidad de un algoritmo se expresa en función del tamaño

del problema que se desea resolver.

Entonces decimos…

• Es una medida de la cantidad de recursos (tiempo y espacio) que un algoritmo necesita.

Tiempo

• La complejidad se asocia a la cantidad de tiempo que necesita el algoritmo para la ejecución de operaciones.

Espacio

• La complejidad es la cantidad de memoria requerida para su ejecución.

Si el recurso es ESPACIO…

• La complejidad del algoritmo esta asociado a la estructura de datos usada en su implementación

Comportamiento de los Algoritmo

• Datos muy ordenados o muy desordenados.• Complejidad del peor caso

Este análisis indica cuantas operaciones tiene que realizar los

algoritmos para garantizar que producirán una solución

Complejidad del caso promedio

• Se busca el promedio de operaciones realizadas para solucionar un promedio considerando todas las posibles entradas con un tamaño determinado.

Análisis del algoritmo cuando crece…

• Tiempo de ejecución• Cuando el tamaño de la entrada crece la función para medir esa

complejidad se denota como T(n).

Notación Asintótica

• Necesitamos analizar la potencia de los algoritmos independientemente de la potencia de la maquina que los ejecute e incluso de la habilidad del programador que los codifique.

• Los problemas pequeños se pueden resolver de cualquier forma.• Los problemas grandes tienen análisis que nos llevan a estudiar el

comportamiento de un algoritmo cuando se fuerza el tamaño del problema al que se aplica matemáticamente.

• N tiende a Infinito (es decir, su comportamiento ASINTÓTICO)

• Asintótico • Se denomina “Asintótico ” al comportamiento de las funciones en

base a su tasa de crecimiento.

• La complejidad del algoritmo se denota según a la notación BIG-O.