complejidad de algoritmos
TRANSCRIPT
Complejidad de los AlgoritmosPaz Morales Vásquez
Docente: Pilar PardoFecha Exposición: 25/03/2014
Qué es la complejidad de un
algoritmo
Para definir la complejidad de un algoritmo es necesario conocer el tamaño del problema a
resolver.
La complejidad se mide en dos recursos que un algoritmo necesita: Tiempo y Espacio.
La complejidad se define por el tiempo que demora un algoritmo para la ejecución de sus operaciones.
Recurso Tiempo
Recurso Espacio
La complejidad se define por la cantidad de memoria requerida para su ejecución.
Cada algoritmo se comporta de forma diferente dependiendo de las variables de entradas asignadas.
Es necesario estudiar su comportamiento considerando su peor caso y mejor caso.
Indica cuantas operaciones tiene que realizar un algoritmo para garantizar que va a ver solución.
Peor Caso
Se busca el promedio de operaciones realizadas para la solución de un problema considerando todas las posibles
entrada.
Caso Promedio
Indica que realiza rápidamente su ejecución.
Mejor Caso
El análisis de algoritmo busca como crece el tiempo de ejecuciónEl análisis de algoritmo busca como
crece el tiempo de ejecución
El análisis de algoritmo busca como crece el tiempo de ejecución
El tiempo de ejecución se denomina: T(n)
Se puede medir: Ejecutando el programa.Calculando sobre el código. Multiplicando por el tiempo de cada instrucción.
Notación Asintótica
La potencia de los algoritmos se analiza independientemente de la potencia de la maquina, el
código y capacidad del programador
Dependiendo del tamaño del problema se determinara como se analizara el comportamiento de un algoritmo
Matemáticamente, cuando N tienda a infinito siempre que algo tiende a infinito
se habla de un comportamiento asintótico.
se denomina asintótica ya que se analiza el comportamiento de las funciones en base a su tasa de crecimiento
Su dominio son los números naturales (N).Estimada por el tiempo de ejecución o espacio de memoria.Se denota como BIG-O.No son negativas.
Se identifican familias de funciones usando como criterio su comportamiento asintótico
A las funciones con el mismo comportamiento se les denomina un
"orden de complejidad (O)"
Complejidad Terminología
0(1) Complejidad constante
O(n2) Complejidad cuadrática
0(log n) Complejidad logarítmica
0(n) Complejidad lineal
O(n log n) Complejidad casi-lineal
0(n^b) Complejidad poli nómica
O(b^n) Complejidad exponencial
O(n!) Complejidad factorial
En conclusión se debe tener en cuenta que antes de realizar un programa es necesario elegir un buen
algoritmo, en donde utilice pocos recursos ya sea el tiempo que lleve ejecutarse y la cantidad de espacio
en memoria que se requiera.