PDF de programación - Capítulo 3 - Diseño de algoritmos iterativos

Diseño de algoritmos iterativos1

Capítulo 3

Cada cosa tiene su belleza, pero no todos pueden
verla.

Confucio

Resumen: En este tema se introducen los conceptos de verificación y derivación de
algoritmos como métodos que nos permiten razonar sobre la corrección de un algoritmo
y su correcta construcción respectivamente.

1.

Introducción

En el capítulo anterior se ha visto la posibilidad de utilizar predicados para definir
conjuntos de estados y cómo es posible especificar un algoritmo mediante dos predicados
llamados precondición y postcondición. El primero describe el conjunto de estados válidos
al comienzo del algoritmo y el segundo el conjunto de estados alcanzables con la ejecución
del algoritmo.

En este capítulo representaremos los estados intermedios de un algoritmo mientras se
ejecuta utilizando predicados, generalmente denominados aserciones o asertos. Escribiendo
asertos entre cada dos instrucciones tenemos un modo de razonar sobre la corrección de
un programa imperativo.

2. Reglas prácticas para el cálculo de la eficiencia

1. Las instrucciones de asignación, de entrada-salida, los accesos a elementos de un
vector y las expresiones aritméticas y lógicas (siempre que no involucren variables
cuyos tamaños dependan del tamaño del problema) tendrán un coste constante, Θ(1).
No se cuentan los return.

2. Para calcular el coste de una composición secuencial de instrucciones, S1; S2 se suman
los costes de S1 y S2. Si el coste de S1 está en Θ(f1(n)) y el de S2 está en Θ(f2(n)),
entonces: Θ(f1(n) + f2(n)) = Θ(máx(f1(n), f2(n))).

3. Para calcular el coste de una instrucción condiciónal:

1Ramón González del Campo es el autor principal de este tema.

25

26

Capítulo 3. Diseño de algoritmos iterativos

if (B) {S1} else {S2}

Si el coste de S1 está en O(f1(n)), el de S2 está en O(f2(n)) y el de B en O(fB(n)),
podemos señalar dos casos para el condiciónal:

Caso peor: O(máx(fB(n), f1(n), f2(n)).
Caso promedio: O(máx(fB(n), f (n)) donde f (n) es el promedio de f1(n) y f2(n).

Se pueden encontrar expresiones análogas a éstas para la clase Omega.

4. Bucles con la forma:

while (B)

{
S
}

Para calcular el coste de tal bucle hay que calcular primero el coste de cada pasada
y después sumar los costes de todas las pasadas que se hagan en el bucle. El número
de iteraciones dependerá de lo que tarde en hacerse falso B, teniendo en cuenta los
datos concretos sobre los que se ejecute el programa y lo grandes que sean.

2.1. Ejemplos de cálculo de complejidad de algoritmos iterativos

De manera práctica, se analizará el código de los algoritmos presentados de arriba hacia

abajo y de dentro hacia fuera.

Búsqueda secuencial

1 bool buscaSec( int v[], int num, int x ) {

int j;
bool encontrado;

j = 0;
encontrado = false;
while ( (j < num) && ! encontrado ) {

encontrado = ( v[j] == x );
j++;

}
return encontrado;

2

3

4

5

6

7

8

9

10

11

12 }

• Caso peor: el elemento buscado x condiciónno está en el vector
◦ Cuerpo del bucle while: 4 (3 en la línea 8 y 1 en la línea 9)
◦ Bucle while:
= 7n + 3
◦ Total: 7n + 3 + 2(inicializaciones) = 7n + 5

∗ ( 4
|{z}

|{z}

j=0..n−1

|{z}

condición

condición

3

|{z}

cuerpo

n

+ 3

) +

• Caso mejor: el elemento buscado x está en la primera posición del vector; solo

se entra una vez en el bucle while
◦ Cuerpo del bucle while: 4
◦ Bucle while: (4 + 3) + 3 = 10

Estructura de Datos y Algoritmos

2. Reglas prácticas para el cálculo de la eficiencia

27

◦ Total: 10 + 2 = 12

Búsqueda binaria

1 int buscaBin( int v[], int num, int x ) {

int izq, der, centro;

izq = -1;
der = num;
while ( der != izq+1 ) {

centro = (izq+der) / 2;
if ( v[centro] <= x )

izq = centro;

else

der = centro;

}
return izq;

2

3

4

5

6

7

8

9

10

11

12

13

14 }

• En esta ocasión no hay caso mejor ni peor, el bucle se ejecuta el mismo número
de veces independientemente de la posición de x en el vector o incluso si x no
aparece en el vector. Aunque el elemento buscado esté en el centro, el bucle
sigue ejecutándose hasta acotar un subvector de longitud 1.
◦ Cuerpo del bucle while:
◦ Bucle while:
|{z}
◦ Total: (8 log(n) + 2) + 2(inicializaciones) = 8 log(n) + 4

|{z}
∗ ( 6
|{z}

= 8 log(n) + 2

| {z }

|{z}if

|{z}

vueltas while

+ 2

log(n)

condición

condición

3

+ 3

= 6

línea 7

) +

2

cuerpo

En caso de que el elemento buscado estuviese repetido, ¿qué posición se devolvería?

Ordenación por inserción

1 void ordenaIns ( int v[], int num ) {

int i, j, x;

for ( i = 1; i < num; i++ ) {

x = v[i];
j = i-1;
while ( (j >= 0 ) && (v[j] > x) ){

v[j+1] = v[j];
j = j-1;

}
v[j+1] = x;

}

2

3

4

5

6

7

8

9

10

11

12

13 }

• Caso peor: el vector está ordenado a la inversa; la segunda parte de la condición

del while se cumple siempre
◦ Cuerpo del bucle while: 6 (4 de la línea 8 y 2 de la línea 9)
◦ Bucle while:
= 10i + 4

+ 4

) +

4

i

j=0..i−1

|{z}

∗ ( 6
|{z}

cuerpo

condición

|{z}

condición

|{z}
Facultad de Informática - UCM

28

Capítulo 3. Diseño de algoritmos iterativos

+ 2

|{z}l5

+ 2

|{z}l6

+ 3

|{z}l11

+ 1

|{z}

i++

= 10i + 12

◦ Cuerpo del bucle for: (10i + 4)
}
◦ Bucle for:
X

((10i + 12)

+ 1

{z

while

n−1

|

n−1

X

) +

1

+ 1

=

(10i + 13) + 2 =

i=1

cuerpo

|

= 10

i=1

}

n−1

n−1

condición

condición

|{z}

|{z}
X

|{z}ini
n(n − 1)

{z
X
= 5n2 − 5n + 13n − 13 + 2 = 5n2 + 8n − 11

13 + 2 = 10

i +

i=1

i=1

2

+ 13(n − 1) + 2 =

• Caso mejor: el vector está ordenado; la segunda parte de la condición del while

no se cumple nunca
◦ Bucle while: 4(condición)
◦ Cuerpo del bucle for: 4 + 2 + 2 + 3 + 1 = 12
◦ Bucle for:
X

(12 + 1) + 1 + 1 =

X

n−1

n−1

i=1

i=1

13 + 2 = 13(n − 1) + 2 = 13n − 11

Ordenación por selección

1 void ordenaSel ( int v[], int num ) {

int i, j, menor, aux;

for ( i = 0; i < num; i++ ) {

menor = i;
for ( j = i+1; j < num; j++ )

if ( v[j] < v[menor] )

menor = j;

if ( i != menor ) {

aux = v[i];
v[i] = v[menor];
v[menor] = aux;

}

}

2

3

4

5

6

7

8

9

10

11

12

13

14

15 }

+ 1

• Caso peor: vector desordenado
◦ Cuerpo del for interno: 3
|{z}if
|{z}l8
|{z}
◦ Bucle for interno: (n − i − 1)
|{z}
|{z}
}
{z
◦ Cuerpo del for externo: 1
+ (6n − 6i − 3)
|{z}l5
|
}

j++
+ 1

j=i+1..n−1

+ 1

{z

( 5

cuerpo

|

f or

= 5

)+ 1

+ 2

= 6n−6i−3

condición

condición

|{z}

+ 1

+ 2

|{z}if

|{z}l10

+ 3

|{z}ini
|{z}l11

+ 2

|{z}l12

+ 1

|{z}

i++

= 6n − 6i + 7

◦ Bucle for externo:
X

n−1

((6n − 6i + 7)
}
|
Estructura de Datos y Algoritmos

{z

cuerpo

i=0

+ 1

)+ 1

condición

condición

|{z}

|{z}

n−1

X

i=0

n−6

= 6

+ 1

|{z}ini

n−1

X

i=0

i+

n−1

X

i=0

8+2 =

2. Reglas prácticas para el cálculo de la eficiencia

29

n(n − 1)

= 6n2 − 6

n + 8n + 2 = 3n2 + 11n + 2
• Caso mejor: vector ordenado; la condición del if más interno no se cumple

+ 8n + 2 = 6n2 −

n2 +

2

6
2

6
2

nunca, y como consecuencia la del más externo tampoco:
◦ Cuerpo del for interno: 4
◦ Bucle for interno: (n − i − 1)(4 + 1) + 1 + 2 = 5n − 5i − 2
◦ Cuerpo del for externo: 1 + (5n − 5i − 2) + 1 + 1 = 5n − 5i + 1
◦ Bucle for externo:

n−1

X

i=0

((5n − 5i + 1) + 1) + 1 + 1 = 5

n − 5

n−1

X

i=0

n−1

X

i=0

n−1

X

i=0

i +

2 + 2 =

= 5n2 − 5

+ 2n + 2 = 5n2 −
¿Qué sucede si el vector está ordenado al revés?

2

n(n − 1)

5
2

n2 +

5
2

n + 2n + 2 =

n2 +

5
2

9
2

n + 2

Ordenación por el método de la burbuja modificado

1 void ordenaBur ( int v[], int num ) {

int i, j, aux;
bool modificado;

i = 0;
modificado = true;
while ( (i < num-1) && modificado ) {

modificado = false;
for ( j = num-1; j > i; j-- )

if ( v[j] < v[j-1] ) {

aux = v[j];
v[j] = v[j-1];
v[j-1] = aux;
modificado = true;

}

i++;

}

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18 }

• Caso peor: El vector está ordenado al revés; se entra siempre en el if :
= 15

+ 2

+ 4

+ 3

+ 1

+ 1

|

cuerpo

{z

j=i+1..n−1

◦ Cuerpo del bucle for: 4
|{z}if
◦ Bucle for: (n − i − 1)
( 15
|{z}
}
◦ Cuerpo del bucle while: 1
|{z}l8
◦ Bucle while:
X

+ 3

((16n − 16i − 11)
|
}

cuerpo

n−2

i=0

condición

|{z}
{z
= 16n(n − 1) − 16

+ 1

1

) +

condición

|{z}l11

|{z}l12

|{z}l13
|{z}
|{z}
+ 16n − 16i − 13
}
|

{z

f or

condición

+ 1

|{z}

i++

|{z}l14

+ 2

j−−

|{z}
= 16n − 16i − 13

|{z}ini
= 16n − 16i − 11

= 16

n−2

X

i=0

n−16

n−2

X

i=0

i−

n−2

X

i=0

8+3 =

)+ 3

condición

|{z}

(n − 2)(n − 1)

2

− 8(n − 1) + 3 =

= 16n2 − 16n − 8n2 + 24n − 16 − 8n + 8 + 3 = 8n2 − 5

Facultad de Informática - UCM

30

Capítulo 3. Diseño de algoritmos iterativos

◦ Total: 8n2 − 5
| {z }

while

+ 2

|{z}ini

= 8n2 − 3

• Caso mejor: El vector está ordenado; nunca se entra en el if y solo se da una

vuelta al while:
◦ Cuerpo del bucle for: 4 + 1 = 5
◦ Bucle for: (n − 1)(5 + 1) + 1 + 2 = 6n − 3
◦ Cuerpo del bucle while: 1 + (6n − 3) + 1 = 6n − 1
◦ Bucle while:

((6n − 1) + 3) + 3 = 6n + 5

◦ Total: 6n + 5 + 2 = 6n + 7

3. Verificación

3.1. Semántica de un lenguaje imperativo

Especificar un algoritmo: encontrar dos predicados P y Q tales que: {P}A{Q}.
Verificar: introducir predicados intermedios entre cada par de instrucciones elemen-
tales:

{P ≡ R0}A1{R1}; ...;{Rn−1}An{Rn ≡ Q}

Si se satisface {Rk−1}Ak{Rk} ∀k entonces se satisface {P}A{Q}.
Buscaremos reglas para determinar si se satisface {Rk−1}Ak{Rk} (reglas de verifica-
ción).

Conocer dichas reglas para cada instrucción del lenguaje es equivalente a conocer la
semántica de éste.

Todas las instrucciones que se definen más adelante cumplen las siguientes reglas generales:

Si se cumple {P}A{Q} podemos conocer otras especificaciones de A. Si P ′ ⇒ P
entonces se cumple {P ′}A{Q}:

P ′ ⇒ P {P}A{Q}

{P ′}A{Q}

(fortalecimiento de la precondición)

Si Q ⇒ Q′ entonces se cumple {P}A{Q′}:

{P}A{Q} Q ⇒ Q′

{P}A{Q′}

Conjunción en la postcondición:

(debilitamiento de la postcondición)

{P}A{Q1} {P}A{Q2}

{P}A{Q1 ∧ Q2}

Disyunción en la precondición:

Estructura de Datos y Algoritmos

3. Verificación

31

{P1}A{Q}

{P2}A{Q}

{P1 ∨ P2}A{Q}

Acabamos de ver que la precondición de una especificación correcta se pue