Notación Big O
Análisis simplificado de la eficiencia de un algoritmo.
- Denota la complejidad en términos del tamaño del parámetro de entrada (normalmente representado con N)
- Independiente de la maquina que ejecuta el algoritmo
- Se examina los pasos computacionales básicos
- Se puede examinar tiempo o espacio
Se pueden examinar el:
- Peor escenario (es el más comunmente usado)
- Mejor esecnario
- Escenario promedio
Reglas de notación Big O:
- Ignora constantes
- Algunos términos "dominan" otros
- Se ignorar los terminos menos dominantes
Los algorítmos de tiempo constante son los que no son afectados por el parámetro de entrada. Denotados por O(1).
El valor de un algoritmo es siempre el mayor de los valores que hacen parte del algoritmo.
En condicionales, al evaluar el peor escenario, se elige la complejidad del flujo de mayor valor.
No hay comentarios:
Publicar un comentario