Análisis de Algoritmos

Jonathan García C. Tesista de Universidad tecnológica de chile

Docente Pilar Pardo H, 26/03/14

• La Complejidad de un algoritmo se representa con el TAMAÑO del PROBLEMA que se desea resolver.

• La complejidad de un algoritmo es una MEDIDA de la cantidad de recursos (espacio – tiempo)que necesita un algoritmo.

Si el recurso es Espacio

• La complejidad es el espacio expresado como función del tamaño del problema. Es decir el espacio en MEMORIA para la ejecución.

Si el recurso es TIEMPO

• La complejidad es el TIEMPO en que el algoritmo se demorar en terminar las OPERACIONES.

• La diversidad en el comportamiento de un algoritmo siempre dependerá de como se ingresen las VARIABLES de entrada.

Por eso siempre es conveniente ESTUDIAR los casos extremos de cada algoritmo.

Complejidad del Peor Caso

• Este análisis corresponde a la traza del algoritmo que realiza la mayor cantidad de ITERACIONES posibles.

Complejidad del caso Promedio

• Busca el PROMEDIO de operaciones realizadas para la solución del problema considerando las posibles entradas con un tamaño determinado.

Tiempo de Ejecución

• Función detonada con T(n), que crece perpendicularmente con los datos de entrada.

• También puede ser calculada físicamente. Enumerando cada proceso y multiplicado por su tiempo de reacción.

Notación Asintótica

Puntos Relevantes.

• Analizar la Potencia de los algoritmos.

• Este análisis es importante cuando el algoritmo se aplica a problemas grandes.

• Los problemas pequeños casi siempre se pueden resolver de cualquier forma.

• No debe olvidar que cualquier técnica de ingeniería, si funciona, acaba aplicándose al problema más grande que sea posible.

Cuando un algoritmo esfuerza su tamaño de problema, podemos decir que: N tiende al Infinito = O

O = Comportamiento Asintótico

• Se denomina FAMILIAS a un conjunto de funciones que comparten un mismo comportamiento asintótico, al cual le denominaremos un orden de complejidad.

• Habitualmente estos conjuntos se denominan O, existiendo una infinidad de ellos.

Complejidad Terminología (Orden)

O(1) Constante

O(LOG n) Logarítmico

O(n) Lineal

O(n LOG n) Casi Lineal

O(n²) Cuadrático

O(𝑎𝑛) Polinomial (a>2)

O(𝑛𝑎) Exponencial (a>2)

O(n!) Factorial