PDF de programación - 1.1 Introducción al Análisis de Algoritmos

J.Dorronsoro, P. Varona, C. Aguirre

Tema 1: Introducción

1

1.1 Introducción al
Análisis de Algoritmos

2

J.Dorronsoro, P. Varona, C. Aguirre

Tiempo Abstracto de Ejecución (TAE)

 ¿Qué analizar en un algoritmo?

Corrección.
Uso de memoria.
Rendimiento (tiempo de ejecución).

 ¿Cómo medir el rendimiento?

Mediante un reloj (tiempo puro de ejecución)

 Intuitivo pero problemático …

Analizando el pseudocódigo: tiempo

abstracto de ejecución (tae)

3

J.Dorronsoro, P. Varona, C. Aguirre

¿Cómo medir el tae?

 Opción 1: Contar el número de sentencias
básicas (líneas acabadas en ; que no son
llamadas a función) que ejecuta el algoritmo
dada una entrada I.

 Opción compleja
 Depende de cómo se escriba el pseudocódigo
 Aporta información innecesaria.

 Esto es, damos un tae de 1 a las sentencias

básicas

 Pero vamos a ver un ejemplo

4

J.Dorronsoro, P. Varona, C. Aguirre

Ejemplo de Cálculo del TAE

Ejemplo: multiplicar matrices cuadradas

(pseudocódigo)

matriz MM(matriz A, matriz B, dim N)

para i de 1 a N:

para j de1 a N:

c[i, j] = 0.;

para k de 1 a N:

c[i, j] += a[i, k] * b[k, j];

devolver C

5

J.Dorronsoro, P. Varona, C. Aguirre

Cálculo del TAE de MM

matriz MM(matriz A, matriz B, dim N)

para i de 1 a N:

para j de1 a N:

c[i, j] = 0.;

para k de 1 a N:

c[i, j] += a[i, k] * b[k, j];

devolver C

Hemos llegado a un tae de la forma f(N) = f( tamaño )

6

)1()1()))((1())(())((),,(211111111NNNkitertaejitertaeiitertaeNBAtaeNiNjNiNjNNiNjNiMM J.Dorronsoro, P. Varona, C. Aguirre

Cálculo del TAE: SelectSort

void SelectSort(Tabla T, ind P, ind U)

i=P;

mientras i<U:

min=i ;

para j de i+1 a U :

si T[j]<T[min] :

min=j ;

swap(T[i],T[min]) ; i++;

Más corto:

void SelectSort(Tabla T, ind P, ind U)

para i de P a U-1:

min= min(T, i, U);

swap(T[i],T[min]);

7

Funcionamiento de SelectSort

J.Dorronsoro, P. Varona, C. Aguirre

 Ejemplo. SelectSort

 Entrada: T=[4,3,2,1], P=1, U=4.

Iteración Operaciones

i=1

i=2

i=3

min=4

swap(T[1],T[4])

min=3

swap(T[2],T[3])

min=3

swap(T[3],T[3])

Tabla

[1,3,2,4]

[1,2,3,4]

[1,2,3,4]

8

J.Dorronsoro, P. Varona, C. Aguirre

Funcionamiento de SelectSort II

En más detalle:

Entrada: T=[4,3,2,1], P=1, U=4.

i=1

Bucle 2

i=2

Bucle 1

Bucle 2

min =1
j=2 ¿T[2]<T[1]? Si → min=2
j=3 ¿T[3]<T[2]? Si → min=3
j=4 ¿T[4]<T[3]? Si → min=4

min=4, swap(T[1],T[4])

min =2
j=3 ¿T[3]<T[2]? Si → min=3
j=4 ¿T[4]<T[3]? No → min=3
min=3, swap(T[2],T[3])

i=3

Bucle 2

min =3
¿T[4]<T[3]? No → min=3
min=3, swap(T[3],T[3])

i=4 Fin (i=U)

1

2

3

4

4 3 2 1

1

2

3

4

1 3 2 4

1 2

3

4

1 2 3 4

1

2

3

4

1 2 3 4

9

J.Dorronsoro, P. Varona, C. Aguirre

TAE de SelectSort

SelectSort funciona con 2 bucles anidados

void SelectSort(Tabla T, ind P, ind U)

i=P;

mientras i<U:

min=i;

para j de i+1 a U:

Bucle 1

Bucle 2

si T[j]<T[min] :

min=j;

swap(T[i],T[min]);

i++;

Vamos a intentar calcular su TAE

10

J.Dorronsoro, P. Varona, C. Aguirre

TAE de SelectSort II

 Cálculo de taeSelectsort(T;P,U):

void SelectSort(Tabla T, ind P, ind U)

i=P;

mientras i<U:

min=i;

bucle 1
U-P
iteraciones

bucle 2
U-i
iteraciones

para j de i+1 a U:

si T[j]<T[min]:

min=j;

swap(T[i],T[min]);

i++;

Bucle de P a U-1

Bucle de i+1 a U

Parece que el número de bucles y su
tamaño determina el tae

11

J.Dorronsoro, P. Varona, C. Aguirre

TAE de SelectSort III

Observando que N=U-P+1 es el tamaño de T, se tiene

Hemos llegado a un tae de la forma f(N)
Pero hay cosas sueltas, sobre todo en los coeficientes
Ejemplo: es el tae de swap 1? ó 3?

12

32/52/32/)1(3)1(412/))(1(3)(413)(41))(34(1)),,(4(1))((1),,(21112 1NNNNNPUPUPUjPUiUUiTtaeiitertaeUPTtaeUPiPUjUPibucleUPiSS2/)1(11NNiPUNNi J.Dorronsoro, P. Varona, C. Aguirre

¿Cómo simplificar y normalizar el TAE?

 Observación: el TAE de MM y SS está dominado por

el bucle más interno

 Opción 2.

 Definir una operación básica y contar el número de veces

que la ejecuta el algoritmo A sobre una entrada I (nA(I))

 Tomar como tiempo abstracto de ejecución del algoritmo A,

para la entrada I el número de operaciones básicas que
ejecuta A sobre I:

taeA(I)= nA(I) .

 Operación básica:

 Se ha de encontrar en el bucle más interno del algoritmo (es la

operación que más veces se ejecuta).

 Debe ser representativa del algoritmo (pero también de otros

que resuelven el mismo problema).

13

J.Dorronsoro, P. Varona, C. Aguirre

Vuelta al psc de MM

Ejemplo: multiplicar matrices (pseudocódigo)

matriz MM(matriz A, matriz B, dim N)

para i de 1 a N:

para j de1 a N:

c[i, j] = 0.;

para k de 1 a N:

c[i, j] += a[i, k] * b[k, j];

devolver C

OB: *
nMM(A, B, N) = N3

14

J.Dorronsoro, P. Varona, C. Aguirre

Vuelta al psc de SelectSort

void SelectSort(Tabla T, ind P, ind U)

i=P;

mientras i<U:

min=i ;

para j de i+1 a U :

si T[j]<T[min] :

min=j ;

swap(T[i],T[min]) ;

i++;

15

J.Dorronsoro, P. Varona, C. Aguirre

Operación básica de SelectSort

 Operación básica

 Debe estar en el bucle más interno

 Ser “representativa” del algoritmo.

 Un buen candidato a ser OB de SelectSort es la

operación

si T[j]<T[min]; .

 Esta operación se denomina “comparación de claves”

(CDC).

 Efectivamente, se encuentra en el bucle más interno.

 Es representativa de SelectSort y de otros muchos

algoritmos de ordenación

16

J.Dorronsoro, P. Varona, C. Aguirre

Análisis del rendimiento de SelectSort
 Cálculo de nSelectSort(T,P,U)

void SelectSort(Tabla T, ind P,ind U)

i=P;

mientras i<U:

min=i;

bucle 1
U-P
iteraciones

bucle 2
U-i
iteraciones

para j de i+1 a U:

si T[j]<T[min]:

min=j;

swap(T[i],T[min]);

i++;

Bucle de P a U-1

Bucle de i+1 a U

17

1111111112 )(1),,(),1,(NjNiNiNijNibucleSelectSortjiNNiTnNTn222)1(NNNN2 J.Dorronsoro, P. Varona, C. Aguirre

Resumiendo …



18

J.Dorronsoro, P. Varona, C. Aguirre

Ejemplo: Búsqueda Binaria

Búsqueda Binaria

ind BBin(Tabla T, ind P, ind U, clave k)

mientras P≤U :
m=(P+U)/2;
si T[m]==k :

devolver m;

else si k < T[m] :

U=m-1;

else :

P=m+1;
devolver error;

Importante: BBin sólo funciona si la tabla T está ordenada.

19

J.Dorronsoro, P. Varona, C. Aguirre

¿Cómo funciona BBin?

 En cada iteración o hay retorno o la tabla se reduce

k<T[m]

k>T[m]

P

m-1

m m+1

U

Si k<T[m]

Si k==m

Si k>T[m]

P

U=m-1

Devolver m

P=m+1

U

 El tamaño de la tabla es aproximadamente la mitad

tras cada iteración

 Si se sale del bucle P≤U porque P > U significa que la

clave buscada k no está en T.

20

J.Dorronsoro, P. Varona, C. Aguirre

OB para BBin

 Mirando el único bucle, un buen candidato a ser

OB es la operación de comparación:

si T[m]==k :

…..

else si k < T[m] :

……

else :

……..

 Aunque hay dos sólo la contamos una vez

 Se trata de nuevo de una operación de

comparación de clave

21

J.Dorronsoro, P. Varona, C. Aguirre

Análisis de rendimiento de BBin

 nBBin(T,P,U,k)= número de iteraciones (P<U) ≤ número de

veces que se puede dividir un número N entre 2.

 Tras cada iteración el nuevo tamaño de la tabla es menor

que la mitad del previo. Por tanto:

k=máximo de divisiones
por 2=número máximo
de iteraciones

 Ejercicio: Realizar el cálculo anterior, contando todas la

sentencias básicas en lugar de solamente la OB

 Solución (opinable): nBBin ≤5 log2N + 2

22

12.......222kNNNNk)N,(T,1,n22BBin1Nlog2kNkk J.Dorronsoro, P. Varona, C. Aguirre

Observaciones sobre el tae

 Observación 1: Parece que para cualquier algoritmo A,

a sus entradas I se les puede asignar un tamaño de
entrada ((I)) y se puede encontrar una cierta función
de N, fA(N) tal que:

taeA(I)=nA(I) ≤ fA((I))

 En los ejemplos vistos

A

I



SelectSort

(T,P,U)

BBin

(T,P,U,k)

U-P+1

U-P+1

fA
N2/2-N/2

lg N

 Observación 2: en el tae hay un término dominante;

los demás importan menos

23

J.Dorronsoro, P. Varona, C. Aguirre

Observaciones sobre tae

 Observación 3: El tae permite

 Generalizar los tiempos de ejecución en función del tamaño de la

entrada.

 Estimar tiempos reales de ejecución.

 Ejemplo: SelectSort con I tal que (I)=N e I’ tal que (I’)=2N

 taeSSort(I)= N2/2+… y

 taeSSort(I’)= (2N)2/2+…=4N2/2+… ~ 4taeSSort(I)

 En general si (I’)=kN se tiene taeSSort(I’) ~k2taeSSort(I)

 Si una tabla con N=1000 tarda 1seg. en ser ordenada,

Entonces

Tamaño

1000

Tiempo real

1s

2000

4s

10000

100s

100000

10000s

24

J.Dorronsoro, P. Varona, C. Aguirre

Ejemplo: método de la Burbuja

 Ordenación por burbuja (BurbujaSort_v1).

BurbujaSort_v1(Tabla T, ind P,ind U)

para i de U a P+1:

para j de P a i-1:

si T[j]>T[j+1]:

swap(T[j],T[j+1]);

 Índice j: burbuja que intenta subir. Si no puede,

cambiamos de burbuja

 Tras cada iteración en i el máximo de la subtabla

está en la posición i

 La tabla se va ordenando de derecha a izquierda

25

Funcionamiento de la Burbuja

J.Dorronsoro, P. Varona, C. Aguirre

 BubbleSort_v1

Burbuja

Entrada: T=[4,3,2,1], P=1, U=4.

i

4

4

4

3

3

2

j

1

2

3

1

2

1

Operaciones

T[1]> T[2] ? Si

swap(T[1],T[2])

T[2]> T[3] ? Si

swap(T[2],T[3])

T[3]> T[4] ? Si

swap(T[3],T[4])

T[1]> T[2] ? Si

swap(T[1],T[2])

T[2]> T[3] ? Si

swap(T[2],T[3])

T[1]> T[2] ? Si

swap(T[1],T[2])

Tabla

3,4,2,1

3,2,4,1

3,2,1,4

2,3,1,4

2,1,3,4

2,1,3,4

26

J.Dorronsoro, P. Varona, C. Aguirre

j=1

j=2

j=3

j=1

j=2

i=4

i=3

1

4

1

3

1

3

2

3

2

4

2

2

3

2

3

2

3

4

4

1

4

1

4

1

T[1]> T[2] ? Si

T[1]> T[2] ? Si

T[1]> T[2] ? Si

1

2

3

4

T[1]> T[2] ? Si

1

3

1

3

1

3

1

2

2

3

4

4

2

2

2

2

2

3

2

3

4

3

1

1

4

1

4

4

3

4

1

4

Swap(T[1],T[2])

Swap(T[2],T[3])

Swap(T[3],T[4])

Swap(T[1],T[2])

3

1

2

2

2

3

1

3

1

4

4

4

T[1]> T[2] ? Si

1

2

3

4

2

1

3

4

Swap(T[2],T[3])

i=2

j=1

1

2

2

1

3

3

4

4

T[1]> T[2] ? Si

1

1

2

2

3

3

4

4

Swap(T[1],T[2])

27

J.Dorronsoro, P. Varona, C. Agui