Análisis de Algoritmos

Conceptos de algoritmia

¿Qué son los algoritmos?

Algoritmo es un conjunto de reglas para efectuar algún cálculo, bien sea a mano o, más frecuentemente, en una máquina

Algoritmia

• Estudio de los algoritmos

• Ciencia que permite evaluar el efecto de factores externos sobre los algoritmos disponibles

• Ciencia que indica la forma de diseñar un nuevo algoritmo para una tarea concreta.

Ejemplo

Eficiencia

• Un algoritmo debe ser rápido y usar la menor cantidad de recursos. Es una relación entre los recursos consumidos, fundamentalmente tiempo y memoria versus los productos obtenidos.

Análisis empírico de algoritmos

• Escribe el programa
• Incluye instrucciones para medir el tiempo de ejecución
• Ejecuta el programa con entradas de diferentes tamaños
• Representa gráficamente los resultados

Ejemplo:

Dado un número n, desarrolle un método para sumar de 1 a n

Incluye instrucciones para medir el tiempo de ejecución

Resultados

La solución de Gauss para sumar números del 1 al n.

• Si n es par, hay n/2 pares
• Si n es impar, hay (n-1)/2 pares
• Cada par suma n+1

Ejemplo

Desventajas:

• Es necesario implementar el algoritmo
• Los resultados pueden no ser indicativos para otras entradas
• Se requiere del mismo entorno para comparar dos algoritmos

Análisis teórico de algoritmos

• Determinar matemáticamente la cantidad de recursos necesarios para cada uno de los algoritmos en función del tamaño de los casos considerados.
• Función de “Tiempo de ejecución”
• Toma en cuenta todas las entradas posibles
• Pseudocódigo
• Define T(n) en función del tiempo de ejecución.
• Independencia con el entorno hardware/software