Analisis de los algoritmos

Autor:Autor: Damary Paquién S. Damary Paquién S.

Docente:Docente: Pilar Pardo H. Pilar Pardo H.

Fecha Exposición:Fecha Exposición:27-03-2014 27-03-2014

UNIDAD IANÁLISIS DE ALGORITMOS

¿QUE ES LA COMPLEJIDAD DE ¿QUE ES LA COMPLEJIDAD DE UN ALGORITMO?UN ALGORITMO?

LA COMPLEJIDAD LA COMPLEJIDAD DE UN DE UN

ALGORITMO ALGORITMO DEPENDE DEL DEPENDE DEL TAMAÑO DEL TAMAÑO DEL PROBLEMA A PROBLEMA A

RESOLVERRESOLVER

Tamaño del problema

Naturaleza de los datos de entrada

Recursos hardware y software

Factores que influyen en la complejidad:

Los algoritmos se comportan de acuerdo a la Los algoritmos se comportan de acuerdo a la información que se le entregue, Variables de información que se le entregue, Variables de Entrada Entrada

Es importante estudiar su comportamiento en casos extremos.

Datos muy Ordenados o muy Desordenados

Complejidad del PEOR CASO: El numero de operaciones que se deben realizar para garantizar una solución.

Complejidad del CASO PROMEDIO: Indica el tiempo promedio obtenido considerando todas las entradas posibles

TIEMPO DE EJECUCIÓNEs definido como una función de entrada

Se definirá T(n) como el tiempo de ejecución de un algoritmo para una entrada de tamaño n.

NOTACION ASINTOTICA

Se describe por una función cuyo dominio son los números naturales N, estimado a partir del tiempo de ejecución de la entrada.La complejidad del algoritmo se denota con la Big-O

Las familias serán congregadas en funciones, usando como Las familias serán congregadas en funciones, usando como criterio de agrupación su comportamiento asintóticocriterio de agrupación su comportamiento asintótico

Estas familias se denominan con O().Estas familias se denominan con O().

CONCLUSIÓNCONCLUSIÓN

La complejidad de un algoritmo depende no solo del espacio en memoria, sino del tiempo que lleve en ejecutarse y que utilice pocos recursos