INTRODUCCIÓN AL ANALISIS DE ALGORITMOS

INTRODUCCIÓN AL
ANALISIS DE ALGORITMOS
Dra. Laura Cruz Reyes
Instituto Tecnológico de Ciudad Madero
México
Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Objetivos del Análisis de Algoritmos
Se analizan los algoritmos con diversos fines:
• Entenderlos
• Mejorarlos
• Seleccionar el más adecuado para resolver
una caso particular de un problema.

Dra. Laura Cruz Reyes1.1 Introd. al Análisis de Algoritmos

Criterios para evaluar algoritmos
•
•
•
•

Corrección
Eficiencia: Complejidad del algoritmo
Sencillez
Optimalidad: Complejidad del problema

Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Corrección
• La relación entre la entrada y salida de un
algoritmo es la esperada.
• Demostración de enunciados acerca de lasrelaciones entre las entradas y salidas.
– Demostraciones formales: axiomas y teoremas.
– Demostraciones informales : simular a mano el
algoritmo en unos cuantos ejemplos pequeños
(pruebas de escritorio).
Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Eficiencia
• El desempeño de un algoritmo se determina
midiendo la cantidad de recursos utilizados en su
ejecución
–Complejidad Espacial: cantidad de memoria ocupada
– Complejidad Temporal: tiempo de ejecución del
algoritmo

• La medición debe ser independiente de:
–
–
–
–

Computadora
Lenguaje de programación
Programador
Detalles de implementación

Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Sencillez
• Sencillo no siempre es sinónimo de eficiencia
• La sencillez facilita:
–Verificación de la escritura correcta del algoritmo
– Depuración
– Modificación

• Si el algoritmo se va a usar con mucha frecuencia,
la eficiencia es importante. Si los requerimientos
son cambiantes, la sencillez puede ser más
importante.
Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Optimalidad
• Un algoritmo es óptimo, si no existe otro
algoritmo, incluso los quetodavía no se
descubren, capaz de resolver el mismo problema
de manera más eficiente.
• El estudio de la complejidad de un problema
pretende determinar la cantidad mínima de trabajo
que requiere efectuarse para resolver un problema
mediante un algoritmo óptimo.
Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Análisis de complejidad de algoritmos
• Análisis teórico(generalizar):
Se determina matemáticamente la cantidad de
recursos requeridos por cada algoritmo como una
función cuya variable independiente es el tamaño
de la entrada.
• Análisis empírico (particularizar):
Las implementaciones de los algoritmos se
ejecutan para diferentes entradas y se comparan en
base a los recursos consumidos
Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de AlgoritmosComplejidad temporal de un algoritmo
• Expresa en T(n) el número de operaciones
básicas que el algoritmo realiza para una
entrada de tamaño n.
• El número de operaciones básicas debe ser
proporcional al total de operaciones.
• Ejemplo de operaciones básicas:
– comparación de x con un elemento del arreglo
– Múltiplicación de dos números reales
Dra. Laura Cruz Reyes

1.1 Introd. alAnálisis de Algoritmos

Complejidad de un algoritmo
1
2
3
4
5
6

read n
producto ←1
for i = 1 to n
read a, b
productoParcial ← a*b
producto ← producto * productoParcial

Operación básica = número de múltiplicaciones
n

T ( n) = ∑ 2 = 2n
i =1

Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Factores que influyen en el
número de operaciones efectuadas
• Tamañode la entrada (n)
– Encontrar x en un arreglo de nombres: el número de
nombres en el arreglo
– Multiplicar dos matrices: las dimensiones de las matrices

• Naturaleza de la entrada (ordenada, desordenada, etc)
– Complejidad del peor caso
– Complejidad del mejor caso
– Complejidad del caso promedio

Dra. Laura Cruz Reyes

1.1 Introd. al Análisis de Algoritmos

Complejidad de peor...