Análisis de algoritmos
1. Introducción.
2. Notaciones asintóticas.
3. Ecuaciones de recurrencia.
4. Ejemplos.
1. Introducción.
Algoritmo: Conjunto de reglas para resolver un problema. Su ejecución requiere unos recursos.
Un algoritmo es mejor cuantos menos recursos consuma. Pero….
Otros criterios: facilidad de programarlo, corto, fácil de entender, robusto…
ALGORITMO
0 ó más entradas
1 ó más salidas
Memoria
Comuni-caciones
º
1. Introducción.
Criterio empresarial: Maximizar la eficiencia.
Eficiencia: Relación entre los recursos consumidos y los productos conseguidos.
Recursos consumidos:
Tiempo de ejecución.
Memoria principal.
Entradas/salidas a disco.
Comunicaciones, procesadores,…
Lo que se consigue:
Resolver un problema de forma exacta.
Resolverlo de forma aproximada.
Resolver algunos casos…
1. Introducción.
Recursos consumidos.
Ejemplo. ¿Cuántos recursos de tiempo y memoria consume el siguiente algoritmo sencillo?
i:= 0
a[n+1]:= x
repetir
i:= i + 1
hasta a[i] == x
Respuesta: Depende.
¿De qué depende?
De lo que valga n y x, de lo que haya en a, de los tipos de datos, de la máquina…
1. Introducción.
Factores que influyen en el consumo de recursos:
Factores externos.
El ordenador donde se ejecute.
El lenguaje de programación y el compilador usado.
La implementación que haga el programador del algoritmo. En particular, de las estructuras de datos utilizadas.
Tamaño de los datos de entrada.
Ejemplo. Procesar un fichero de log con N líneas.
Contenido de los datos de entrada.
Mejor caso ™. El contenido favorece una rápida ejecución.
Peor caso (tM). La ejecución más lenta posible.
Caso promedio (tp). Media de todos los posibles contenidos.
1. Introducción.
Los factores externos no aportan información sobre el algoritmo.
Conclusión: Estudiar la variación del tiempo y la memoria necesitada por un algoritmo respecto al tamaño de la entrada y a los posibles casos, de forma aproximada (y parametrizada).
Ejemplo. Algoritmo de búsqueda secuencial.
Mejor caso. Se encuentra x en la 1ª posición:
tm(N) = a
Peor caso. No se encuentra x:
tM(N) = b·N + c
Ojo: El mejor caso no significa tamaño pequeño.
1. Introducción.
Normalmente usaremos la notación t(N)=…, pero ¿qué significa t(N)?
Tiempo de ejecución en segundos. t(N) = bN + c.
Suponiendo que b y c son constantes, con los segundos que tardan las operaciones básicas correspondientes.
Instrucciones ejecutadas por el algoritmo. t(N) = 2N + 4.
¿Tardarán todas lo mismo?
Ejecuciones del bucle principal. t(N) = N+1.
¿Cuánto tiempo, cuántas instrucciones,…?
Sabemos que cada ejecución lleva un tiempo constante, luego se diferencia en una constante con los anteriores.
1. Introducción.
El proceso básico de análisis de la eficiencia algorítmica es el conocido como conteo de instrucciones (o de memoria).
Conteo de instrucciones: Seguir la ejecución del algoritmo, sumando las instrucciones que se ejecutan.
Conteo de memoria: Lo mismo. Normalmente interesa el máximo uso de memoria requerido.
Alternativa: Si no se puede predecir el flujo de ejecución se puede intentar predecir el trabajo total realizado.
Ejemplo. Recorrido sobre grafos: se recorren todas las adyacencias, aplicando un tiempo cte. en cada una.
1. Introducción.
Conteo de instrucciones. Reglas básicas:
Número de instrucciones t(n) ? sumar 1 por cada instrucción o línea de código de ejecución constante.
Tiempo de ejecución t(n) ? sumar una constante (c1, c2, …) por cada tipo de instrucción o grupo de instrucciones secuenciales.
Bucles FOR: Se pueden expresar como un sumatorio, con los límites del FOR como límites del sumatorio.
n
? k =
i=1
b
? k =
i=a
n
? i =
i=1
b
? ri =
i=a
k n
k(b-a+1)
n(n+1)/2
rb+1 – ra
r – 1
n
? i2 ˜
i=1
n
? i2 di =
0
n
(i3)/3 ] =
0
(n3)/3
1. Introducción.
Conteo de instrucciones. Reglas básicas:
Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir. ¿Existe una cota inferior y superior del número de ejecuciones? ¿Se puede convertir en un FOR?
Llamadas a procedimientos: Calcular primero los procedimientos que no llaman a otros. t1(n) , t2(n) , …
IF y CASE: Estudiar lo que puede ocurrir. ¿Se puede predecir cuándo se cumplirán las condiciones?
Mejor caso y peor caso según la condición.
Caso promedio: suma del tiempo de cada caso, por probabilidad de ocurrencia de ese caso.
1. Introducción.
Ejemplos. Estudiar t(n).
for i:= 1 to N
for j:= 1 to N
suma:= 0
for k:= 1 to N
suma:=suma+a[i,k]*a[k,j]
end
c[i, j]:= suma
end
end
Funcion Fibonacci (N: int): int;
if N< 0 then
error(‘No válido’)
case N of
0, 1: return N
else
fnm2:= 0
fnm1:= 1
for i:= 2 to N
fn:= fnm1 + fnm2
fnm2:= fnm1
fnm1:= fn
end
return fn
end
1. Introducción.
Ejemplos. Estudiar t(n).
for i:= 1 to N do
if Impar(i) then
for j:= i to n do
x:= x + 1
else
for j:= 1 to i do
y:= y + 1
end
end
end
A[0, (n-1) div 2]:= 1
key:= 2
i:= 0
j:= (n-1) div 2
cuadrado:= n*n
while key< =cuadrado do
k:= (i-1) mod n
l:= (j-1) mod n
if A[k, l] ? 0 then
i:= (i + 1) mod n
else
i:= k
j:= l
end
A[i, j]:= key
key:= key+1
end
Página siguiente  |