Jonathan Higuera
Complejidad de Algoritmos
COMPLEJIDAD DE UN ALGORITMO
• La complejidad de un algoritmo depende del tamaño del problema que deseamos resolver
Entonces se puede diferir que la complejidad de un algoritmo se puede medir en relación a la cantidad de
TIEMPO y ESPACIO que un algoritmo necesita
Entonces la complejidad es la cantidad de tiempo en que se demora el algoritmo para la ejecución de la operación
TIEMPO como factor
ENTONCES LA COMPLEJIDA ESTA EN LA MEMORIA QUE SE REQUIERE PARA EJECUTARLA
Si uno de los recursos es el espacio …
CADA UNO DE LOS ALGORITMOS SE COMPORTARA DIFERENTE DEPENDIENDO DE LOS DATOS DE ENTRADA QUE SE LE ENTREGA
• Los algoritmos se comportan de distinta manera de acuerdo a como se les ingrese la información.
• Por esto es necesario analizar como se comportan en los casos extremos, utilizando datos muy ordenados o datos muy desordenados.
VARIABLES DE ENTRADA
PEOR CASO
El peor caso consiste en verificar cuántas operaciones tienen que realizar los algoritmos para llegar a la solución, entre más operaciones se hagan el caso es peor
CASO PROMEDIO
Se Busca un promedio de operaciones que se realizan para la solución de un problema. Se considera todas las entradas posibles con un tamaño determinado
Mejor Caso
El mejor caso, es aquel en el que el algoritmo utiliza la menor cantidad de recursos (tiempo, por ejemplo) para solucionar el problema.
Cuando el tamaño de una entrada crece, la función para medir dicha complejidad es denotada como T(n)
Tiempo de Ejecución.
Se analiza el Comportamiento del algoritmo cuando n (tamaño) tiende a infinito
Notación Asintótica
La complejidad del algoritmo se denota con Big-0
O(1) Complejidad constante O(n2) Complejidad cuadrática
O(log n) Complejidad logarítmica O(n) Complejidad lineal
O(n log n) Complejidad casi-lineal O(n^b) Complejidad polinómica
O(b^n) Complejidad exponencial O(n!) Complejidad factorial