Análisis de
Algoritmos
Por: Dra. Nancy Pérez Castro
Introducción
Laeficiencia de un algoritmo se relaciona
con la cantidad de recursos que requiere
para obtener una solución al problema
(menor cantidad de recursos, mayor
eficiencia).
2
Definición complejidad
El costo o complejidad temporal de un algoritmo es
el tiempo empleado por éste para ejecutarse y
proporcionar un resultado a partir de los datos de
entrada.
El costo o complejidad espacial de un algoritmo
como cantidad de memoria requerida (suma total del
espacio que ocupan las variables del algoritmo),
antes, durante y después de su ejecución.
3
¿Qué puede afectar al evaluar?
El lenguaje de programación.
La computadora en donde se ejecute.
El compilador utilizado.
La experiencia del programador.
Datos de entrada.
Valor de las variables.
Llamado a funciones.
4
¿Cómo evitar estos problemas?
Para evitar estos problemas, tiene sentido estimar
el costo de los algoritmos con independencia de los
programas que los implementen.
Lo que se pretende no es medir el costo temporal
exacto (segundos) y la cantidad de memoria (bytes).
Sino obtener un valor estimado de estos valores
mediante el cálculo de estos valores mediante el
cálculo de número de operaciones que será preciso
realizar y el número de variables a emplear.
5
No será fácil
El costo aproximado será difícil de evaluar
debido a que diferentes operaciones cuestan
un tiempo diferente.
3.25*9.5 3+9
Existen librerías de las que a priori se
desconoce el tiempo de ejecución.
6
Cálculo
Para simplificar el cálculo, se hará una
estimación del costo de algoritmo a través de
una agrupación de las operaciones realizadas en
tres clases diferentes y asumiendo un costo
temporal único para cada una:
Operaciones aritméticas to
Asignaciones ta
Comparaciones tc
7
Operaciones Elementales (OE)
Es aquella operación cuyo tiempo de
ejecución se puede acotar superiormente por
una constante que solamente dependerá de la
implementación particular usada.
No depende de parámetros.
No depende de la dimensión de los datos de
entrada.
8
Ejemplo
Realizar un algoritmo que calcule la siguiente función
100
y= ∑ x
i= 1
y = 0 /*1/
i = 1 /*2/
mientas (i <= 100) hacer /*3/
y = y+x /*4/
i = i+1 /*5/
fin mientras /*6/
9
Ejemplo
y = 0 /*1/
i = 1 /*2/
mientas (i <= 100) hacer /*3/
y = y+x /*4/
i = i+1 /*5/
fin mientras /*6/
/*1/ ta
/*2/ ta
/*3/ 100*tc (comparaciones de repetición del bucle)
/*4/ 100*(to+ta)
/*5/ 100*(to+ta)
/*6/ tc (comparación de salida del bucle) 10
Ejemplo
/*1/ ta
/*2/ ta
/*3/ 100*tc (comparaciones de repetición del bucle)
/*4/ 100*(to+ta)
/*5/ 100*(to+ta)
/*6/ tc (comparación de salida del bucle)
La estimación de tiempo en función de las operaciones
realizadas será:
T = 2ta + 100*(tc+2to+2ta)+tc
T = 202ta+202to+101tc
11
Ejemplo
Si se analiza con detalle el problema que se está
resolviendo, se puede llegar fácilmente a la conclusión
que sumar 100 veces la variable x es lo mismo que
multiplicar x por 100.
100
y= ∑ x
i= 1
Entonces:
Y = 100 * x
Costo temporal sería:
T = to+ta
12
Concepto de talla de un problema
Ademásde medir el tiempo de ejecución de
un algoritmo en función de sus operaciones
básicas, también hay que considerar que el
costo del algoritmo puede depender de los
datos de entrada del algoritmo.
Diferentesvalores de entrada puede generar
diferentes tiempos de ejecución.
13
Ejemplo
/*1/ y = 0 n
/*2/ i = 1 y= ∑ i
i= 1
/*3/ mientras (i <= n) hacer
/*4/ y = y+i
/*5/ i = i+1
/*6/ fin mientras
14
Ejemplo
/*1/ y = 0 ta n
y= ∑ i
/*2/ i = 1 ta i= 1
/*3/ mientras (i <= n) hacer n*tc
/*4/ y = y+i n*(to+ta)
/*5/ i = i+1 n*(to+ta)
/*6/ fin mientras tc
T = 2ta + n * (tc+2to+2ta)+tc
15
Talla del problema
Sedenomina talla de un problema al valor o
conjunto de valores asociados a la entrada
del problema y que representa una medida
del tamaño del problema respecto de otras
entradas posibles.
16
Ejercicio
Búsqueda secuencial. Se aplica cuando no existe
ningún conocimiento previo sobre la ordenación
de los elementos del conjunto en donde se va a
realizar la búsqueda.
Realizar el código de la función de búsqueda. Se
asumirá que los datos son de tipo entero y que,
como resultado de la búsqueda, solo interesa
saber si el elemento x está o no en el vector.
17
bool BusquedaSecuencial (int v[], int n, int x)
//v es el arreglo que contiene los datos
//n es el número de elementos en el vector
//x es el dato buscado
{
int i; /*1*/
bool enc = false; /*2*/
i = 0; /*3*/
while (i < n) /*4*/
{
if (v[i] == x) /*5*/
enc = true; /*6*/
i = i + 1; /*7*/
}
return enc; /*8*/
}
18
/*2*/ ta
/*3*/ ta
/*4*/ n*tc + tc (repeticiones + salida)
/*5*/ n*tc
/*6*/ ¿?
/*7*/ n*(to+ta)
Por lo tanto, el costo no depende solo de la talla sino de la
configuración de los datos de entrada. Es en estos casos donde se
debe evaluar el algoritmo en términos de mejor, peor y caso
promedio.
19
Mejor, peor y caso promedio
Mejor caso. Un algoritmo tiene un mejor caso cuando
los parámetros del problema llevan a realizar el
menor número de pasos posibles, y el tiempo que
tarda el algoritmo se expresa como Tm.
Peor caso. Cuando los parámetros del algoritmo lleva
a realizar el máximo número de pasos, se expresa
como Tp.
Caso medio. Es expresado por la media de los pasos
realizados en función de los casos posibles, Tµ.
20
Instancia de un problema
Unainstancia de un problema corresponde a
todas las configuraciones diferentes de la
entrada, de una talla determinada, que dan
lugar al mismo comportamiento del
algoritmo.
21
Regresando al ejercicio...
Mejor caso
Cuando la condición de la línea 5 siempre se
evalúa como falsa y no se realiza nunca la
línea 6.
Peor caso
Cuando los elementos del arreglo fueran tales
que hicieran que la condición de la línea 5
fuera cierta.
22
Ejercicio
Dado el siguiente fragmento de código, determina que
hace y realiza tres casos de prueba de escritorio y
calcula su costo temporal a priori.
i = 0; min = 0;
while (i < n) {
if (A[i] < A[min])
min = i;
++i;
}
23
