PDF de programación - Tema 2: Diseño de Algoritmos - Algoritmos y Estructuras de Datos

Algoritmos y Estructuras de Datos

Tema 2: Diseño de Algoritmos

Algoritmos y Estructuras de datos DIT-UPM

1

Contenidos

! 1. Algoritmos recursivos

" 1.1 Algoritmos recursivos. Recursión simple
" 1.2 Algoritmos con vuelta atrás y ejemplos

! 2. Complejidad de los algoritmos
! 3. Algoritmos de búsqueda y su complejidad
! 4. Optimización de algoritmos

Algoritmos y Estructuras de datos DIT-UPM

2

Complejidad de Algoritmos
! Un mismo problema se puede resolver con muy

diferentes algoritmos

! Para hacer una implementación debemos
seleccionar uno. Criterios para seleccionar:
" Seleccionar el que emplea menor número de

recursos (por ejemplo, memoria, cómputo, ancho
banda)

" Seleccionar el algoritmo menos complejo (por ejemplo

número de líneas de código)

" Seleccionar aquel del que tenemos implementación

probada

Algoritmos y Estructuras de datos DIT-UPM

3

Complejidad de Algoritmos

! Los algoritmos se analizan para

" Fijar una clasificación basada en los criterios de los

análisis

" Predecir el comportamiento antes de implementar

#  Predecir eficiencia en el uso de recursos
#  Predecir escalabilidad. Simples pruebas no bastan para

saber si un algoritmo será escalable en:
•  Analizar un genoma, banco de proteínas, red de sensores,
medidas astrofísicas o geológicas, movimientos de clientes
bancarios, …

•  Hay que predecir que pasará cuando se ejecuten en

escenarios reales trabajando con datos reales

Algoritmos y Estructuras de datos DIT-UPM

4

Complejidad de Algoritmos

!  Criterio mas empleado: tiempo de ejecución
"  Cuantificable (hay varias formas) y fácil de comparar
"  Tiempos de ejecución suelen ser el origen de cuellos de botella

!  El tiempo de ejecución de los algoritmos depende de

varios factores:
"  Plataforma hardware. Por ejemplo, cache de multicores puede
generar resultados muy diferentes para algoritmos muy similares

"  Lenguaje de programación y su ejecución
"  Estilos de eficiencia de los programadores

!  Notación Big O: análisis teórico que asume algunas

simplificaciones
"  Estimar medida de tiempo de ejecución en función de la cantidad

de datos tratados

Algoritmos y Estructuras de datos DIT-UPM

5

Medir cantidad de datos
!  Necesitamos medir la cantidad de los datos tratados

para poder estimar tiempos de ejecución, y después
encontrar como se relacionan
!  Algunos ejemplos de medidas:

Algoritmo
Buscar en una lista
Multiplicar dos matrices
Ordenar una lista
Recorrer un árbol binario
Resolver un problema en un grafo

Tamaño de datos
Número de elementos en la lista
Tamaños de las matrices
Número de elementos en la lista
Número e nodos en el árbol
Número de nodos y/o arcos en el grafo

Algoritmos y Estructuras de datos DIT-UPM

6

Tiempos de ejecución

! No buscamos valores numéricos; buscamos

estimaciones de coste en función de la cantidad
de datos tratados

! Formas de medir tiempos de ejecución

"  Tiempo medio:

#  Valor ideal, pero difícil de predecir

de forma teórica

"  Mejor caso:
#  Poco útil
"  Peor caso:

Peor Caso

Tiempo medio

Mejor caso

#  Es una estimación pesimista
#  Los análisis de complejidad asumen que lo importante es la

escalabilidad y que el tamaño de los datos de entrada puede ser muy
grande

Algoritmos y Estructuras de datos DIT-UPM

7

Porque algoritmos eficientes?
! Supongamos que trabajamos sobre n=106 valores
" Por ejemplo: operaciones registradas en un banco en

un año

! Supongamos que un PC tarda 1 sec en

leer/procesar n datos

! Pero si en algoritmo es de orden n*n. Tarda en

ejecutarse 106sec = 11 días

Algoritmos y Estructuras de datos DIT-UPM

8

Función de complejidad (1)
! El resultado del análisis de complejidad será

una función f(n), donde n es la cantidad de datos
con la que tratamos
" f(n) representa el trabajo que el algoritmo debe hacer

para obtener el resultado

! f(n) es solo una estimación. En la práctica, el
esfuerzo depende de los valores concretos que
tengan los valores de entrada
" En la práctica, dos conjuntos de datos de entrada del
mismo tamaño, tienen tiempos de ejecución distintos

Algoritmos y Estructuras de datos DIT-UPM

9

Función de complejidad (2)
! Lo que representamos en la función es como de

rápido va creciendo el coste de ejecución
según crece el tamaño de los datos tratados
" Si f(n) es una función polinomial de orden r la

complejidad será O(nr)
! Órdenes mas utilizados

Orden
O(1)

Interpretación
El tiempo de ejecución está limitado por una constante que no dependen del número de datos de
tratados
El tiempo de ejecución es directamente proporcional al número de datos de tratados

El tiempo de ejecución es proporcional al cuadrado del número de datos de tratados

O(n)
O(n2)
O(kn)
O(log n) El tiempo de ejecución crece en una función logarítmicamente proporcional a la del de los datos
10

El tiempo de ejecución crece de forma exponencial en función del número de datos de entrada

tratados

Algoritmos y Estructuras de datos DIT-UPM

Valor de las funciones

! Supongamos que el ordenador ejecuta 109

operaciones/sec. Los tiempos totales son del
orden de:

n

n
10
.01µs
20
.02µs
30
.03µs
40
.04µs
50
.05µs
100
.1µs
103
1µs
104 10µs
105 100µs 1.66ms
106

f(n)
2n
n4
n3
n log n
1µs
10µs
1µs
.03µs
1ms
160µs
8µs
.09µs
1s
810µs
27µs
.15µs
18m
2.56ms
64µs
.21µs
13d
6.25ms
125µs
.28µs
100ms
1ms
4×1013y
.66µs
16.67m 3.17×1013y 32×10283y
1s
9.96µs
115.7d 3.17×1023y
130µs 100ms 16.67m
11.57d
3171y 3.17×1033y
31.71y 3.17×107y 3.17×1043y

10s
1ms 19.92ms 16.67m

n2
.1µs
.4µs
.9µs
1.6µs
2.5µs
10µs
1ms

n10

10s
2.84h
6.83d
121d
3.1y
3171y



70000

60000

50000

40000

30000

20000

10000

0

n

Algoritmos y Estructuras de datos DIT-UPM

11

Valor de las funciones (2)

2n

n2

n3

n log n
n

log n

100000

10000

1000

100

10

1

n

2n

n3

n2

n log n

n

log n

O(1) O(log n) O(n) O(n log n) O(np) O(2n) O(n!)

Algoritmos y Estructuras de datos DIT-UPM

12

!  Suma de array de reales

Algunos Ejemplos

for (int i=0; i<n; i++)

"  f(n)=c n -> O(n)

Z[i] = A[i] + B[i]; // esto tarda en ejecutarse c

!  Multiplicación de todos los elementos de un array

for (int i=0; i<n; i++)

z = z * A[i]; // esto tarda en ejecutarse c2

"  f(n)=c2 n -> O(n)

!  Multiplicación de 2 arrays

for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
Z[i,j] = A[i] * B[j];
"  f(n)=c3 n2, O(n2)

!  Un programa que hace las tres cosas

"  f(n)=c n + c2 n + c3 n2 -> O(n2)

Algoritmos y Estructuras de datos DIT-UPM

13

Simplificación de la función

! Funciones como



c n + c2 n + c3 n2

son incomodas de usar y comparar

! Nos interesan los valores dominantes. Nos
quedamos el termino que hace crecer mas
rápidamente la función O(n2)
" Aquello que nos crea los cuellos de botella

! Las constantes como c y c2 no son

significativas porque dependen de las máquinas
y lenguajes



Algoritmos y Estructuras de datos DIT-UPM

14

Análisis de algoritmos

!  Sentencias simples con operaciones simples

"  Ejemplo: a=b+c;
"  O(1)

!  Sentencias simples con llamadas a método

"  Ejemplo: m(x)
"  La función y complejidad del algoritmo que implementa el método

!  Secuencia de sentencias

"  Ejemplo: m(x); a=b+c;
"  La complejidad la determina aquella que es dominante

!  Bucles un número fijo de veces

"  Ejemplo: for (int i=0; i < 20; i++) m(x);
"  La función de complejidad es la operación ejecutada multiplicada

por el número de iteraciones

Algoritmos y Estructuras de datos DIT-UPM

15

Análisis de algoritmos

!  Sentencias condicionales
if (cond) then O(1)
body1 f1(n)

else

body2 f2(n)

endif

una, será esa

"  La complejidad es la dominante de las dos alternativas. Si solo hay

!  Bucles con una condición que depende del número de

datos
"  Ejemplo: for (i=1; i<n; i++) if x > y a=b+c;
"  O(n)

Algoritmos y Estructuras de datos DIT-UPM

16

Análisis de algoritmos

!  Bucles anidados o bucles con cuerpos no simples:

"  Ejemplo:

for (i=1; i<n; i++)
for (j=n; j>= i+1; j--)
if (A[j-1] > A[j]) {
temp = A[j-1];
A[j-1] = A[j];
A[j] = tmp;
"  Complejidad O(n2)

!  Recursividades

"  Las recursividades simples se pueden tratar como bucles
"  En otros casos hay que emplear aproximaciones recurrentes
que dependen del algoritmo, y se hacen suponiendo niveles de
recursiones de peor caso

Algoritmos y Estructuras de datos DIT-UPM

17

Ejemplo práctico: serie Fibonacci

! La serie de Fibonacci es:

1,1,2,3,5,8,13, …

!  La función de la serie devuelve 1 para los argumentos 1 y

2 y los siguientes son la suma de los dos anteriores

!  Dos soluciones, cual debemos utilizar?

Algoritmo 1
int f(int i) {
if (i <= 2)
return 1;
return f(i-2)+f(i-1);
}



Algoritmo 2
int f(int i) {
int a=1; int b=1; int c=1;
while (i-- > 2) {
c=a+b; a=b; b=c;
}
return c;
}

Algoritmos y Estructuras de datos DIT-UPM

18

Ejemplo práctico: serie Fibonacci

Algoritmo 1
int f(int i) {
if (n <= 2)
return 1;
return f(i-2)+f(i-1);
}

Algoritmo 2
int f(int i) {
int a=1; int b=1; int c=1;
while (i-- > 2) {
c=a+b; a=b; b=c;
}
return c;
}



!  El algoritmo 2 es O(n), donde n es el valor para el que queremos

Algoritmos y Estructuras de datos DIT-UPM

19

calcular la función

!  El algoritmo 1 es O(2n). Para calcular f(x)-> f sigue los pasos:

"  Paso 1: 2 llamadas a f
"  Paso 2: 2*2 llamadas a f
"  Paso 3: 2*2*2 llamadas a f
"  Paso k: 2*2k-1 llamadas a f