Complejidad de los Algoritmos

UNIVERSIDAD TECNOLOGICA DE CHILE

Alumno: Francisco Cordero.Docente: Pilar Pardo.Fecha: 28/03/2014

¿Que es la complejidad

de un algoritmo?

La complejidad de un

algoritmo esta relacionado

directamente del

TAMAÑO del

algoritmo

a resolver

La complejidad de un algoritmo será determinadapor la cantidad de TIEMPO y de ESPACIO que el algoritmo necesita.

En el caso del ESPACIO

La complejidad del algoritmo estará determinada por la cantidad de MEMORIA REQUERIDA para ejecutar el algoritmo.

En el caso del TIEMPO

La complejidad del algoritmo estará determinada por la cantidad de TIEMPO para ejecutar el algoritmo.

Estructura de datos

Internas

Externas

Dinámicas

Estáticas

Lineales

No Lineales

-Pilas

-Listas

-Colas

-Base de datos

-Archivos

El comportamiento de un algoritmo dependerá de como se le entreguen las VARIABLES DE ENTRADA que tiene el algoritmo

Se aconseja estudiar el comportamiento de un algoritmo en sus casos mas extremos

En el MEJOR caso (ORDENADO) y en el PEOR caso (DESORDENADO)

Complejidad del PEOR caso

Indica el numero de operaciones que se deben realizar para GARANTIZAR una SOLUCION

Complejidad PROMEDIO

Se determinara el promedio de las OPERACIONES que se realizaran para Solucionar un problema, teniendo en cuenta las posibles variables de entradaCon un tamaño determinado.

TIEMPO DE EJECUCIÓN

Este determinante de la complejidad se

denota como T(n) , y va en directa proporcionalidad con el tamaño de entrada del algoritmo.

Complejidad TerminologiaO(1) Complejidad constanteO(n2) Complejidad cuadráticaO(log n) Complejidad logarítmicaO(n) Complejidad linealO(n log n) Complejidad casi – linealO(n^b) Complejidad polinómicaO(b^n) Complejidad exponencialO(n!) Complejidad factorial

Tipos de complejidades

Conclusión