Complejidad de los Algoritmos

Nombre: Sergio Ormeño

Asignatura: Análisis de algoritmos

Profesora: Pilar Pardo

Fecha: 26/03/2014

¿Qué es la complejidad de un algoritmo?

Es una medida, la cual se mide en función del tamaño de problema.

Se expresa en la cantidad de recursos (tiempo de ejecución y espacio en memoria) que un algoritmo necesita.

El tamaño del problema

Es la cantidad de tiempo que necesita el algoritmo para la ejecución de operaciones.

Recurso Tiempo

Recurso Espacio

Es la cantidad de memoria requerida que necesita el algoritmo para ejecutarse.

Se diferencia de acuerdo a como se le entregue la información.

El comportamiento de un algoritmo

los algoritmos se estudian en base a su comportamiento, muy ordenados o muy desordenados.

El peor caso

Es cuando realiza las operaciones con el máximo de recursos.

El caso promedio

Busca el promedio de operaciones considerando todas las posibles entradas con un tamaño determinado.

Tiempo de ejecución

Busca saber como crece el tiempo de ejecución cuando el tamaño de la entrada crece.

Notación asintótica

Se basa en analizar la potencia de un algoritmo en condiciones extremas, independiente de la maquina y de la

habilidad del programador .

La complejidad es una forma de medir que tan rápido se ejecuta un algoritmo.

Conclusión

Conclusión

Su importancia radica en que mientras más grande sea la entrada, los recursos para ejecutarse aumentan.