Análisis de algoritmo
Claudio Troncoso
La complejidad de un algoritmo se refleja en la dificultad del
problema
Si el recurso es espacio
Se tomara encuenta la cantidad de memoria requerida para su ejecución y como se ordenara el algoritmo
Si el recurso es Tiempo
Se asocia a la cantidad de tiempo que necesita el algoritmo para su ejecución
Caso Promedio
Procesos los cuales llegan a una solución, sin embargo pueden ser menos
Caso Mejor
Mínimo de procesos para llegar a una solución
Tiempo de ejecución
Cuando los datos de entrada son grandes el tiempo de ejecución es mayor
Se denota como T(n)
Se denota por la Big-O
Complejidad Terminología
O(1) Complejidad Constante
O(n^2) Complejidad Cuadrática
O(Log n) Complejidad Logarítmica
O(n) Complejidad Lineal
O(n log n) Complejidad Casi-Lineal
O(n^b) Complejidad Poli nómica
O(b^n) Complejidad Exponencial
O(n!) Complejidad Factorial