Date post: | 27-Jul-2015 |
Category: |
Documents |
Upload: | francisco-cordero-cordero |
View: | 116 times |
Download: | 3 times |
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