PDF de programación - Análisis de Algoritmos

Análisis de Algoritmos.

Segundo Curso, Grado en Ingeniería Informática

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Carlos Aguirre
José Dorronsoro
Pablo Varona

2

Capítulo 1

Introducción al análisis de
algoritmos

1.1. Medida de eficacia de algoritmos

¿Qué analizar en un algoritmo? Tenemos diferentes opciones.

Corrección

Uso de memoria

Rendimiento en ejecución: cuánto va a tardar

En este curso nos vamos a centrar en la tercera opción, es decir, en estudiar
el tiempo de ejecución de un algoritmo. Para llevar a cabo esta tarea podemos
considerar diferentes opciones:

Opción 1. Medir la duración de la ejecución con un reloj según los siguientes
pasos:
(1) escoger un pseudocódigo ⇒ (2) programa ⇒ (3) ejecutable ⇒ (3) selec-
cionar entradas y ⇒ (4) ejecutar sobre las entradas midiendo tiempos con un
reloj

Esta aproximación se demuestra poco práctica ya que tiene muchas depen-

dencias

Depende de la pericia del programador.

Depende de la calidad del compilador.

Depende del tipo de máquina y, sobre todo, de los datos sobre los que se
ejecute.

3

4

CAPÍTULO 1. INTRODUCCI ÓN AL AN ÁLISIS DE ALGORITMOS

Principal pega: el tiempo empleado sobre unas entradas no dice nada sobre lo
que se tardará sobre otras.

Opción 2. Análisis de tiempos abstractos de ejecución sobre pseudocódigo.

Es la que usaremos en el curso.

1.2. Tiempo abstracto de ejecución

Para medir los tiempos abstractos de ejecución de un algoritmo necesitamos
definir la unidad de tiempo abstracto. La unidad de tiempo que vamos a consid-
erar será la “sentencia elemental”, esto es, una línea simple de pseudocódigo que
no contenga ninguna llamada a otra función. (Por supuesto, tendremos que tener
cuidado con estas sentencias “no elementales”.)

Definiremos tae o tiempo abstracto de ejecución como el número de
unidades de tiempo abstracto ejecutadas, es decir el número de sentencias el-
ementales ejecutadas para unas entradas dadas.

Más formalmente, para un algoritmo A y una entrada I definimos tA(I) como

el número de sentencias elementales de A que se ejecutan sobre la entrada I.

La base del análisis está por tanto en el pseudocódigo.
Ejemplo 1. Ordenación por selección

SelectSort(tabla T,ind P, ind U)

(1) i=P;
(2) mientras i < U :

| m= min(T,i,U):

(2) | swap(T[i],T[m]);

// NO es sentencia elemental; hay que hacer algo
// tampoco lo es ... pero la tomamos como tal!

| i++;

ind min(tabla T, ind P, ind U)

(1) m=P;
(2) para i de P+1 a U:
| si T[i]<T[m]:

(2) |

m=i;

(1) devolver m;

// la tomamos como sentencia simple

Las instrucciones marcadas con (1) son instrucciones que se ejecutan una sola
vez, las instrucciones marcadas con (2) se ejecutan repetidas veces. Un ejemplo
de funcionamiento del algoritmo sobre la tabla
”4 3 2 1”

Seguimos la evolución de los índices i y m:
i=1 m=4 swap(T[1],T[4]) 1 3 2 4

1.2. TIEMPO ABSTRACTO DE EJECUCI ÓN

5

i=2 m=3 swap(T[2],T[3]) 1 2 3 4
i=3 m=3 swap(T[3],T[3]) 1 2 3 4

Vamos a calcular primero tmin(T, P, U ) tiempo abstracto de ejecución de la
función min, es decir, cuantas ejecuciones de sentencias elementales hace min
para la tabla T entre P y U . Hay que observar que la condición T[m]>T[i] no
siempre es cierta y por tanto la asignación m=i no siempre se ejecuta.
Para superar esto, nos ponemos en el caso de “más trabajo”, suponiendo que
siempre se cumple la condición y acotamos el número real de ejecuciones mediante
un ≥. Por lo tanto, esto nos lleva a

tmin(T, P, U ) ≤ 2 + 3 × N úmero de iteraciones del bucle.

donde contamos 3 sentencias elementales a lo sumo dentro del bucle de min.
Claramente el bucle se ejecuta U − P veces, lo que nos lleva a

tmin(T, P, U ) ≤ 2 + 3(U − P ).

Por lo tanto, tomando el caso particular P = 1, U = N nos da

tmin(T, P, U ) ≤ 2 + 3(N − 1).

Con esto ya podemos empezar a estimar tss(T, P, U ). Como mezcla sentencias
básicas con la que contiene la llamada a min, que ejecuta un número variable de
sentencias básicas en cada iteración, llegamos a:

tss(T, P, U ) = 1 +

(4 + tmin(T, i, U )) + 1

i=P

≤ 2 + 4(U − P ) +

(2 + 3(U − i))

U−1

i=P

= 2 + 4(N − 1) + 2(N − 1) + 3

(U − i)

= 6N − 4 + 3

j = 6N − 4 + 3

N (N − 1)

2

U−1

U−1

i=P

N−1

=

3
2

N 2 +

j=1

N − 4.

9
2

Ejemplo 2. Búsqueda binaria

6

CAPÍTULO 1. INTRODUCCI ÓN AL AN ÁLISIS DE ALGORITMOS

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

(2)

(2)

(1)

mientras P <= U :

devolver M;

| m= (P+U)/2;
| si T[M]==k :
|
| else si k < T[M] :
|
| else :
|

U=M-1;

P=M+1
devover err;

El número de sentencias elementales que se ejecutan en cada iteración del

bucle es mayor o igual que cinco:
una debida a la comprobación de la condición del bucle más,
al menos cuatro, instrucciones dentro del bucle (como antes, no todas se ejecutan
en cada iteración, por lo que de nuevo acotamos con un ≥.
Con esto se tiene

tBBin(T, P, U, ) ≤ 2 + 5 ∗ n. de iteraciones.

Por lo tanto es necesario estimar el número de iteraciones. Para ello estimamos
el tamaño de la subtabla después de cada iteración.

Tras cada iteración:

iteración
tamaño de la subtabla
Supongamos que el número de elementos N de la tabla T es 2l−1 < N ≤ 2l

.......
.......

1
N/2

N/4

2

3

N/8

para algún l ∈ N . Por lo tanto, l − 1 < log2 N ≤ l, esto es,

l = log2(N )

donde el operador es el operador techo (a modo de ejemplo, 2,7 = 3)
Entonces, si el algoritmo llega a la iteración l, tras la iteración se seguiría buscando
en una tabla de tamaño < N/2l ≤ 1, lo que no es posible. Por lo tanto, no hay
más de log2(N ) iteraciones y se tiene que

TBBin(T, P, U, k) ≤ 2 + 5log2N

Observación El trabajo máximo se produce agotando todas las iteraciones

(P > U ), lo cual ocurre cuando la clave a buscar k no está en T .

Los ejemplos anteriores nos permiten establecer las siguientes observaciones:

1.2. TIEMPO ABSTRACTO DE EJECUCI ÓN

7

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 fA
tal que

taeA(I) ≤ fA(τ (I))

Hemos visto:

A

I

τ

SelectSort

BBin

(T,P,U) U-P+1
(T,P,U,k) U-P+1

3

2 N 2 + ...

5log2 N + 2

(1.1)

fA

2. El tae nos permite generalizar los tiempos abstractos de ejecución
para nuevas entradas y además estimar tiempos reales de ejecución, como
podemos ver en el siguiente ejemplo.

Consideremos SelectSort con una entrada I tal que τ (I) = N y otra
entrada I tal que τ (I) = 2N . Se tiene entonces que

taeSSort(I) =

3
2

(2N )2 + .... = 4(

N 2 + ....) ≈ 4taeSSort(I).

3
2

En general si I tiene un tamaño k veces mayor que el tamaño de I (i.e
τ (I) = kN )

taeSSort(I) = k2taeSSort(I)

(1.2)

Supongamos ahora que un programa que implemente SelectSort tarda 1
segundo al ordenar una tabla de N = 1000 elementos. Entonces

1000
Tamaño
Tiempo real de ejecución 1 seg

2000
4 seg

10000
100 seg

100000

10000 seg

3. En taeSSort(N ) = 3

2 N 2 + 6N − 6 el término que más importa para valores
grandes de N es el correspondiente a N 2. En el caso de taeBBin(N ) =
2 + 5log2 N el término de mayor peso es log2 N.

4. El tae tal como lo hemos definido sigue siendo algo artificioso ya que su

valor puede depender de cómo se escriba el pseudocódigo.

Por ejemplo los códigos básicamente iguales de abajo dan lugar a taes dis-
tintos.

8

CAPÍTULO 1. INTRODUCCI ÓN AL AN ÁLISIS DE ALGORITMOS

Código 1

D=A+B+C;

tae 1

Código 2

E=A+B;
F=C+E;
D=F;

tae 3

Por tanto, hay que hacer algo a este respecto.

5. En SelectSort el término N 2 y en BBin el término log2 N vienen de
ejecutar el bucle mas interno. Por esta razón vamos a cambiar la unidad
de medida que usamos a la hora de calcular el tae. En lugar de contar el
número de sentencias básicas que se ejecutan lo que vamos a considerar es
el número de veces que se ejecuta una cierta operación básica.

1.3. Operación básica de un algoritmo

La operación básica (OB) de un algoritmo A es una sentencia elemental de

A que además cumple las siguientes condiciones:

1. Debe aparecer en el bucle más interno del algoritmo. Debe ser la instrucción

que más veces se ejecuta.

2. Debe ser una operación representativa del algoritmo.

Ejemplo 1. En el caso de SelectSort la instrucción de comparación de claves

(cdc)

si T[i]<T[m]

cumple las condiciones 1 y 2 al estar en el bucle mas interno y tratarse de una
comparación de claves. La instrucción

m=P;

no siempre se ejecuta, y la instrucción

i++;

es una instrucción general de muchos algoritmos.

Ejemplo 2. En el caso de BBin también tomaremos la cdc como operación

básica la instrucción

1.3. OPERACI ÓN B ÁSICA DE UN ALGORITMO

9

si T[M]==K
...
else si K < T[M]
...
else si

A partir de ahora usaremos en vez de tabstractoej. la nueva medida nA(I), que
es el número de veces que el algoritmo A ejecuta su operación básica (OB) sobre
la entrada I. Veamos tres ejemplos, dos ya conocidos y uno nuevo.

Ejemplo 1: Búsqueda binaria
Para calcular nBBin(T, P, U, k) analizamos los bucles del algoritmo vemos que
la operación básica siempre se ejecuta una vez para cada iteración del bucle. Por
tanto se tiene:

nBBin ≤ 1 ∗ numero de ejecuciones del bucle = log2N

(1.3)

Ejemplo 2: Ordenación por selección
Calculamos nSSort(T, P, U ) usando como OB la cdc. Sólo hay cdcs en min y
dentro de la función min el número de veces que se ejecuta la operación básica
depende de los valores de entrada. El coste total del algoritmo será, tomando
P = 1 y U = N .

N−1

N−1

U

i=P +1

nSSort(T, 1, N ) =

nmin(T, i, N ) =

i=1

i

N − i =

N 2
2

− N
2

(1.4)

Ejemplo 3: Método de la burbuja
Para el método de la burbuja para ordenación veremos dos versiones.

V