PDF de programación - Tema 3.1: Introducción a la eficiencia de algoritmos

Tema 3.1: Introducción a la eficiencia de

algoritmos

Diseño y Análisis de Algoritmos

Tema 3.1: Introducción a la eficiencia de algoritmos

Contenidos

Contenidos

1

Introducción

2 Eficiencia en espacio

3 Análisis de algoritmos iterativos

URJC

DAA

2 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Introducción

Eficiencia de Algoritmos

¿Qué recursos necesitan los algoritmos?

En espacio (memoria)

En tiempo (número de operaciones)

Otros:

Ancho de banda

URJC

DAA

3 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Introducción

Eficiencia de Algoritmos

¿Por qué estudiamos la eficiencia de algoritmos, cuando parece que
hay otras características del software más importantes?

Amigabilidad

Buen estilo de programación

Comentarios

Corrección

Escalabilidad

Funcionalidad

Mantenibilidad

Modularidad

Rendimiento

Robustez

Seguridad

Simplicidad

Tiempo de programación

. . .

La eficiencia nos va a ayudar a alcanzar el resto de características

URJC

DAA

4 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Eficiencia en espacio

Modelo de memoria

Modelo de memoria

Código del algoritmo

Datos estáticos

Variables globales

Llamadas a subprogramas

Parámetros

Variables locales

Memoria dinámica

URJC

DAA

5 / 24

CódigoDatos estáticosMontículo (heap)Pila / Subprogramas Tema 3.1: Introducción a la eficiencia de algoritmos

Eficiencia en espacio

Llamadas a subprogramas

1 main(...){
2 ...
3 A(..)
4 ...
5 }
6
7 A(...){
8 ...
9 B(..);

10 ...
11 }
12

13 B(...){
14 ...
15 C(..);
16 ...
17 }
18
19 C(...){
20 ...
21 }

URJC

DAA

6 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Eficiencia en espacio

Árbol de llamadas

Árbol de llamadas

Proceso de llamadas

URJC

DAA

7 / 24

mainABCmainABC123456 Tema 3.1: Introducción a la eficiencia de algoritmos

Eficiencia en espacio

Estado de la pila

URJC

DAA

8 / 24

datos dinámicosdatos dinámicosdatos dinámicosdatos dinámicosdatos dinámicosdatos dinámicosdatos dinámicosAcodigodatos estáticoscodigodatos estáticosAcodigodatos estáticosBAcodigodatos estáticosBCAcodigodatos estáticosBAcodigodatos estáticoscodigodatos estáticos Tema 3.1: Introducción a la eficiencia de algoritmos

Eficiencia en espacio

Recursividad

Caso recursivo: Fn+2 = Fn+1 + Fn

Casos base F1 = F2 = 1

Observación: ¿Por qué los nodos de un mismo nivel aparecen con el mismo
color, a pesar de corresponder a llamadas con diferentes parámetros?

URJC

DAA

9 / 24

F5F4F3F2F3F2F2F1F1 Tema 3.1: Introducción a la eficiencia de algoritmos

Eficiencia en espacio

Estado de la pila

Espacio(n) ∈ Θ(n)

URJC

DAA

10 / 24

F5F5F5F5F5F5F5F5F5F5F5F5F5F5F4F4F4F4F4F4F4F4F3F3F2F3F3F1F3F4F2F3F3F2F3F5F3F1F5F3F5 Tema 3.1: Introducción a la eficiencia de algoritmos

Eficiencia en espacio

Llamadas a subprogramas

La complejidad depende de la profundidad del árbol de llamadas

Para ilustrar esto se han coloreado los nodos de un mismo nivel en el
árbol con el mismo color

Las llamadas de un mismo color aparecen en el mismo nivel en la pila,
al igual que en el árbol

La complejidad también depende de los recursos que consuma cada
subprograma ejecutado (cada llamada)

Parámetros de los subprogramas

Variables locales a los subprogramas

URJC

DAA

11 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Un ejemplo: Insert-sort

Algoritmo de ordenación por inserción directa (insert-sort)

URJC

DAA

12 / 24

2479918324791832477918324579183parte ordenadaparte desordenadaelemento a insertarInsert-sortelemento a comparar247918355247918355 Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Un ejemplo: Insert-sort

Pseudocódigo y coste por línea

Insert-sort(A)

Coste No de veces

1 FOR j=2 to length(A)
2
3

val = A[j]
// Inserta A[j] en la secuencia
// ordenada A[1..j-1]
i = j-1
WHILE (i>0) y (A[i]>val)

4
5
6
7
8

A[i+1] = A[i]
i = i-1

A[i+1] = val

C1
C2

0
C4
C5
C6
C7
C8

n
n − 1
n − 1
n
n − 1
n
n
j=2 tj
j=2(tj − 1)
j=2(tj − 1)
n − 1

n = length(A)
tj = no de veces que se repite el bucle de la línea 5, para un
determinado valor de j

URJC

DAA

13 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Un ejemplo: Insert-sort

Ignoramos el coste concreto de cada operación básica

Cada línea l tardará un determinado tiempo o coste, que denotamos
por Cl

La función de coste o tiempo, en función del tamaño del vector n es:

T (n) = C1n + C2(n − 1) + C4(n − 1) + C5

tj +

n

n

C6

(tj − 1) + C7

n

j=2

(tj − 1) + C8(n − 1)

j=2

j=2

tj depende del vector de entrada particular

URJC

DAA

14 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Un ejemplo: Insert-sort

Mejor caso (vector ordenado de menor a mayor)

tj = 1, para todo j

T (n) = C1n + C2(n − 1) + C4(n − 1) + C5(n − 1) + C8(n − 1)

= (C1 + C2 + C4 + C5 + C8)n − (C2 + C4 + C5 + C8)

= K1n + K2 ∈ Θ(n)

El orden de T (n) es lineal

¡Para el orden, el valor de las constantes no importa!

URJC

DAA

15 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Un ejemplo: Insert-sort

Peor caso (vector ordenado de mayor a menor)

tj = j (valor máximo para cada j)

En primer lugar observamos que:

n

j=2

j =

n(n + 1)

2

− 1

n

j=2

(j − 1) =

n(n + 1)

2

− 1 − (n − 1) =

n(n − 1)

2

URJC

DAA

16 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Un ejemplo: Insert-sort

Sustituyendo:



n(n − 1)


2

+

C7
2

+ C7



C6

C5

2

=

+

C6
2

T (n) = C1n + C2(n − 1) + C4(n − 1) + C5

n(n − 1)



2

n(n + 1)

2



+

− 1

+ C8(n − 1) =



n−

C5
2

− C6
2

− C7
2

+ C8

n2 +

C1 + C2 + C4 +

(C2 + C4 + C5 + C8) = K1n2 + K2n + K3 ∈ Θ(n2)

El orden de T (n) es cuadrático

URJC

DAA

17 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Caso medio frente a caso peor

En ocasiones se puede calcular el caso medio, pero nos centraremos
en el estudio de caso peor debido a:

El caso peor representa un cota superior para cualquier entrada,
dándonos una garantía de que el algoritmo no tardará más

El caso peor suele ocurrir con frecuencia

En una búsqueda, ocurre cuando el elemento buscado no se encuentra

El tiempo medio suele ser tan malo como el peor en términos
asintóticos

Si en el insert-sort hay que insertar el elemento hasta la posición j/2, el
tiempo también sale cuadrático

URJC

DAA

18 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Otro ejemplo: Bubble-sort

Algoritmo de ordenación “burbuja” (bubble-sort)

URJC

DAA

19 / 24

parte ordenadaparte desordenadaBubble-sortelementos a comparar247918352479183524791835247518392475183924571839elementos a intercambiar Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Otro ejemplo: Bubble-sort

Pseudocódigo

// for 1

// for 2

for(int i=0; i<v.length-1; i++)
{

for(int j=v.length-1; j>i; j--)
{

1 void bubbleSort(int []v)
2 {
3
4
5
6
7
8
9
10
11
12
13
14
15 }

int aux = v[j-1];
v[j-1] = v[j];
v[j] = aux;

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

}

}

}

URJC

DAA

20 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Operaciones de un bucle de n iteraciones

1 inicialización

n comparaciones

Tiempo de ejecutar el cuerpo del bucle n veces

n incrementos

1 última comparación para salir del bucle

n

Tbucle = 1inic. +

(1comp. + Tcuerpo + 1incr.) + 1última comp.

URJC

DAA

21 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Tiempo en el mejor caso

1a forma: simplemente contando operaciones

For 1:

1inic. + (n − 1)incr. + (n − 1)comp. + 1última comp. = 2n

For 2:

(n − 1)inic. +(n − 1) + (n − 2) + . . . + 1
(n− 1) + (n− 2) + . . . + 1

comp. + (n − 1)última comp.

decr. +(n− 1) + (n− 2) + . . . + 1

comp. del IF

Sumando todo:
Tmejor(n) = 2n + 2(n − 1) + 3

n(n − 1)

2

=

3
2

n2 +

5
2

n − 2 ∈ Θ(n2)

URJC

DAA

22 / 24

 + 1

(1 + 1 + 1) + 1 + 1

Tmejor(n) = 1 +

For 1:

i+1

j=n−1

n−2

i=0

1 + 1 +
n−2

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Tiempo en el mejor caso

2a forma: usando la fórmula del bucle

Tmejor(n) = 1inic. +

[1comp. + TFor 2 + 1incr.] + 1última comp.

For 2:

Tmejor(n) = 1inic. +

i=0

i+1

j=n−1

[1comp. + 1comp. IF + 1incr.] + 1última comp.

URJC

DAA

23 / 24

Tema 3.1: Introducción a la eficiencia de algoritmos

Análisis de algoritmos iterativos

Tiempo en el mejor caso

Simplificando:

Tmejor(n) = 2 +

n−2

i=0



3

i+1

j=n−1

4 +
n−2

El sumatorio interno suma (n − i − 1) veces. Por tanto:

Tmejor(n) = 2 + 4(n − 1) +

3(n − i − 1) =

2 + 4n − 4 + 3n(n − 1) − 3

i=0

(n − 1)(n − 2)

2

− 3(n − 1)

Tmejor(n) =

n2 +

3
2

5
2

n − 2 ∈ Θ(n2)

URJC

DAA

24 / 24