Complejidad de los algoritmosCRISTIAN FUENTEALBA

La La complejidad complejidad del algoritmo del algoritmo depende del depende del tamaño del tamaño del problemaproblema

Mientras más complejo sea un algoritmo, más espacio y tiempo de ejecución necesitara.

Recurso TiempoRecurso Tiempo

Implica el tiempo de ejecución que requiere el algoritmos para ejecutarse.

Recurso EspacioRecurso Espacio

Implica la cantidad de memoria que Implica la cantidad de memoria que necesita el algoritmo para ejecutarse.necesita el algoritmo para ejecutarse.

Recurso Espacio.LA COMPLEJIDAD ESTA ASOCIADA A LAS ESTRUCTURAS DE DATOS UTILIZADAS EN SU CONSTRUCCIÓN

ComportamientoComportamiento

CADA ALGORITMO SE COMPORTA DE ACUERDO CADA ALGORITMO SE COMPORTA DE ACUERDO A LASA LAS

VARIABLES DE ENTRADA QUE SE LE ENTREGE.VARIABLES DE ENTRADA QUE SE LE ENTREGE.

Para estudiarlos, es mejor basarse Para estudiarlos, es mejor basarse en casos extremos.en casos extremos.

MUY ORDENADOSMUY ORDENADOS

DESORDENADOSDESORDENADOS

Complejidad del peor Complejidad del peor CasoCaso

Complejidad del Complejidad del Caso promedioCaso promedio

Realiza el camino más complejo dentro del Realiza el camino más complejo dentro del algoritmoalgoritmo

Se realiza un promedio de las operaciones para Se realiza un promedio de las operaciones para solucionar el problema.solucionar el problema.

Tiempo de Tiempo de ejecuciónejecución

Cuando el tamaño de la entrada crece la función para Cuando el tamaño de la entrada crece la función para medir complejidad se denota como:medir complejidad se denota como:

T(n)T(n)Se puede medir contando instrucciones a ejecutar y Se puede medir contando instrucciones a ejecutar y multiplicando por el tiempo de ejecución.multiplicando por el tiempo de ejecución.

Notación AsintóticaNotación Asintótica

Se analiza la potencia del algoritmoSe analiza la potencia del algoritmo

Esta enfocado en resolver el problema más grande.Esta enfocado en resolver el problema más grande.

Los problemas pequeños se resuelven de cualquier forma.Los problemas pequeños se resuelven de cualquier forma.

Cuando n tiende a infinito.Cuando n tiende a infinito.

Se denomina asintótica por que se analiza el algoritmo en función de Se denomina asintótica por que se analiza el algoritmo en función de su tasa de crecimientosu tasa de crecimiento.

FamiliasFamilias

Se denominan familias a un conjunto de Se denominan familias a un conjunto de funciones que comparten un mismo funciones que comparten un mismo comportamiento asintótico, al que se le comportamiento asintótico, al que se le denomina “ORDEN DE COMPLEJIDAD”denomina “ORDEN DE COMPLEJIDAD”

Estos conjuntos se denominan O, y existe una Estos conjuntos se denominan O, y existe una infinidad de ellos.infinidad de ellos.