PDF de programación - Tema 1. Análisis de algoritmos - Parte I. Estructuras de Datos

Programa de teoría
Parte I. Estructuras de Datos.

1. Abstracciones y especificaciones.
2. Conjuntos y diccionarios.
3. Representación de conjuntos mediante árboles.
4. Grafos.

Parte II. Algorítmica.

1. Análisis de algoritmos.
2. Divide y vencerás.
3. Algoritmos voraces.
4. Programación dinámica.
5. Backtracking.
6. Ramificación y poda.

A.E.D.

Tema 1. Análisis de algoritmos.

1

PARTE II: ALGORÍTMICA

Tema 1. Análisis de algoritmos.

1.1. Introducción.

1.2. Notaciones asintóticas.

1.3. Ecuaciones de recurrencia.

1.4. Ejemplos.

A.E.D.

Tema 1. Análisis de algoritmos.

2

1

1.1. Introducción.

• Algoritmo: Conjunto de reglas para resolver un
problema. Su ejecución requiere unos recursos.

0 ó más
entradas

ALGORITMO

1 ó más
salidas

• Un algoritmo es mejor cuantos menos recursos

consuma. Pero....

• Otros criterios: facilidad de programarlo, corto,

fácil de entender, robusto...

A.E.D.

Tema 1. Análisis de algoritmos.

3

1.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...

A.E.D.

Tema 1. Análisis de algoritmos.

4

2

• Recursos consumidos.

1.1. Introducción.

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...

A.E.D.

Tema 1. Análisis de algoritmos.

5

1.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 blog: número de mensajes.

– Contenido de los datos de entrada.

• Mejor caso (tm). 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.

A.E.D.

Tema 1. Análisis de algoritmos.

6

3

1.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.

A.E.D.

Tema 1. Análisis de algoritmos.

7

1.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.

A.E.D.

Tema 1. Análisis de algoritmos.

8

4

1.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.

A.E.D.

Tema 1. Análisis de algoritmos.

9

1.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,

0

10

5

con los límites del FOR como límites del sumatorio.
nΣ k =
bΣ ri =

bΣ k =
nΣ i2 ≈

(i3)/3 ] =

k(b-a+1)

nΣ i =

i=1

(n3)/3

n(n+1)/2

kn

rb+1 – ra
r – 1

i=a

i=1

i=1

i=a

n

n
∫ i2 di =
0

A.E.D.

Tema 1. Análisis de algoritmos.

1.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.

A.E.D.

Tema 1. Análisis de algoritmos.

11

• Ejemplos. Estudiar t(n).

1.1. Introducción.

Funcion Fibonacci (N: int): int;
if N<0 then

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

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

A.E.D.

Tema 1. Análisis de algoritmos.

12

6

1.1. Introducción.

• Ejemplos. Estudiar t(n).
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

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

else

i:= k
j:= l
end
A[i, j]:= key
key:= key+1

end

A.E.D.

Tema 1. Análisis de algoritmos.

13

1.1. Introducción.

• Ejemplos. Estudiar t(n) en el caso promedio, para las

instrucciones de asignación. Usar probabilidades.

i:= 1
mientras i ≤ n hacer

si a[i] ≥ a[n] entonces

a[n]:=a[i]

finsi
i:= i *2

finmientras

cont:=0
para i:= 1,...,n hacer

para j:= 1,...,i-1 hacer

si a[i] < a[j] entonces
cont:= cont + 1

finsi
finpara

finpara

A.E.D.

Tema 1. Análisis de algoritmos.

14

7

1.1. Introducción.

• El análisis de algoritmos también puede ser a posteriori:

implementar el algoritmo y contar lo que tarda para
distintas entradas.

• En este caso, cobran especial importancia las

herramientas de la estadística: representaciones gráficas,
técnicas de muestreo, regresiones, tests de hipótesis, etc.

• Hay que ser muy específicos, indicar: ordenador, S.O.,
condiciones de ejecución, opciones de compilación, etc.
t(N)
(ms)

Pentium IV a 2,66Mhz
512 Mb de RAM, DDR
HD Serial ATA, 60 Gb.
S.O. Linux RedHat 8
(único proceso en ejec.)
Compilado con -o3

N

0

10

20

30
A.E.D.

40

Tema 1. Análisis de algoritmos.

15

•

1.1. Introducción.

Indicamos los factores externos, porque influyen en los
tiempos (multiplicativamente), y son útiles para comparar
tiempos tomados bajo condiciones distintas.

• La medición de los tiempos es un estudio experimental.
• El análisis a posteriori suele complementarse con un estudio

teórico y un contraste teórico/experimental.

t(N)

• Ejemplo. Haciendo el

estudio teórico del
anterior programa,
deducimos que su
tiempo es de la forma:
c1n2 + c2 n + c3

• Podemos hacer una re-
gresión. ¿Se ajusta
bien? ¿Es correcto el
estudio teórico?

c1n2 + c2n + c3

10

20

30

40

0
A.E.D.

Tema 1. Análisis de algoritmos.

N

16

8

1.1. Introducción.

• El contraste teórico/experimental permite: detectar posibles
errores de implementación, hacer previsiones para tamaños
inalcanzables, comparar implementaciones.

• Sin el estudio teórico, extraer conclusiones relevantes del

tiempo de ejecución puede ser complejo.

• Ejemplo. Programa

“cifras.exe”:
– N= 4, T(4)= 0.1 ms
– N= 5, T(5)= 5 ms
– N= 6, T(6)= 0.2 s
– N= 7, T(7)= 10 s
– N= 8, T(8)= 3.5 min

)
s
m

(

)

N

(
t

30

25

20

15

10

5

0

1

2

3

4

5

6

7

• ¿Qué conclusiones podemos extraer?
• El análisis a priori es siempre un estudio teórico previo a la
implementación. Puede servir para evitar la implementación,
si el algoritmo es poco eficiente.
A.E.D.

17

Tema 1. Análisis de algoritmos.

8 N

1.2. Notaciones asintóticas.

• El tiempo de ejecución t(n) está dado en base a

unas constantes que dependen de factores
externos.

• Nos interesa un análisis que sea independiente de

esos factores.

• Notaciones asintóticas: Indican como crece t,

para valores suficientemente grandes
(asintóticamente) sin considerar constantes.

• O(t): Orden de complejidad de t.
• Ω(t): Orden inferior de t, u omega de t.
• Θ(t): Orden exacto de t.

A.E.D.

Tema 1. Análisis de algoritmos.

18

9

1.2.1. Definiciones.
Orden de complejidad de f(n): O(f)

• Dada una función f: N → R+, llamamos orden de f

al conjunto de todas las funciones de N en R+
acotadas superiormente por un múltiplo real
positivo de f, para valores de n suficientemente
grandes.

O(f)= { t: N → R+ / ∃ c ∈ R+, ∃ n0 ∈ N, ∀ n ≥ n0;

t(n) ≤ c·f(n) }

A.E.D.

Tema 1. Análisis de algoritmos.

19

1.2.1. Definiciones.

Observaciones:
• O(f) es un conjunto de funciones, no una

función.

• “Valores de n suficientemente grandes...”: no nos

importa lo que pase para valores pequeños.
• “Funciones acotadas superiormente por un
múltiplo de f...”: nos quitamos las constantes
multiplicativas.

• La definición es aplicable a cualquier función de N

en R, no sólo tiempos de ejecución.

A.E.D.

Tema 1. Análisis de algor