Repository navigation
9 Algoritmos
Un algoritmo es un proceso finito de pasos precisos para resolver un problema.
Finito: Termina despues de un numero finito de pasos.
Indefinido: Cada paso se define con precision.
Tiene una salida
Tiene una entrada bien definida
Determinista
Son efectivos
Es un metodo para estimar el consumo de recursos de un algoritmo.
Para descubrir caracteristicas de un algoritmo en orden a evaluar
Comparar un algoritmo con otro con la misma aplicación
Clasificar problemas y algoritmos por dificultad
Mejorar la comprension y mejorar implementaciones y algoritmos.
Sistema de la computadora
Compilador
Lenguaje de programacion
Sistema operativo
Desarrollador
Tamaño de entrada
Aplicaciones que corren en la computadora
Tiempo (CPU)
Espacio en memoria
Ancho de banda
Espacio en el disco
Dispositivos de periferia
Cualquier recurso en la computadora
Clasifica dos tiempos tomados por un algoritmo
Representa el algoritmo como un tamaño funcional en la entrada
Complejidad de tiempo es estimado por contando instrucciones elementales.
Frecuencia a la que se ejecuta la CPU
se mide en hercios o gugahercios
Mayor frecuencia es mayor velocidad de reloj (cantidad de ciclos de reloj por unidad de tiempo)
Cuántas instrucciones puedo ejecutar por ciclo de reloj
Ciclos por instruccion
Instructor por ciclo
Instrucciones por segundo
Instrucciones elementales vs instrucciones compuestas
Instrucciones que siempre toman el mismo tiempo
No preocuparnos sobre cuantos ciclos de instrucciones necesitamos que sean ejecutadas
Operaciones basicas (+, -, *, %, ^)
Operaciones logicos ( ==, !=, and, or)
Operadores bit a bit ( <<, >>)
Jumps ( returns values, method calls)
Asignación, acceso a estructuras indexadas
El trabajo puede ser calculado con una funcion del tamaño de la entrada al algoritmo
Es posible expresar una aproximación de estas funciones usando una notacion matematica llamada orden de magnitudes o Big-O