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

Búsqueda en array de enteros
!  Si un array no está ordenado, no hay mejor algoritmo

 

que una búsqueda lineal del primero al último

static final int NINGUNO = -1; // marca de no encontrado

  static int busquedaLineal(int buscado, int[] a) {

if (buscado == a[p]) return p;

for (int p = 0; p < a.length; p++) {

}
return NINGUNO;

}

!  Complejidad O(n)

"  Tiempo medio en encontrar un elemento que está

(suponiendo que no están repetidos) n/2
"  Peor caso (no se encuentra en el array) n
Algoritmos y Estructuras de datos DIT-UPM

3

Búsqueda en array de String

! Igual que la búsqueda de enteros, excepto

" Si utilizamos str1==str2 buscamos objetos
" Si utilizamos str1.equals(str2) buscamos valores

  static final int NINGUNO= -1; // marca de no encontrado

  static int busquedaLineal (String buscado, String[] a) {

for (int p = 0; p < a.length; p++) {

}
return NINGUNO;

if (buscado.equals(a[p])) return p;



}

Algoritmos y Estructuras de datos DIT-UPM

4

Búsqueda en array de Object

! Igual que la búsqueda en array de String.

" Si las instancias de Object tienen definido el método
" Si utilizamos ==, buscamos un objeto en

equals, podemos buscar por valor

concreto


! En Java no podemos hacer hacer un

algoritmo genérico para cualquier tipo de
datos. Lo mas genérico es:
"  static int busquedaLineal (Object buscado, Object[] a)
" El compilador convierte automáticamente int a

su envoltorio (Integer). Pero no los array (int[] a
Integer[])

Algoritmos y Estructuras de datos DIT-UPM

5

Java sobrecargar equals
!  La clase Object es la superclase de todas las clases e

incluye la declaración:

public boolean equals(Object obj)

!  Su implementación por defecto es una comparación por
referencia (el objeto y el parámetro son el mismo objeto)

!  Con frecuencia queremos una comparación por valor

"  La clase String sobrecarga este método y compara los strings por

valor

!  Nuestras clases pueden sobrecargar equals y comparar

con nuestras reglas
"  Una clase Punto puede sobrecargar equals y comparar dos

posiciones con criterios propios
#  Por ejemplo: la distancia entre los dos puntos es menor que una

constante EPSILON

Algoritmos y Estructuras de datos DIT-UPM

6

Arrays/Listas ordenadas

! Un array/lista está ordenado en orden

ascendente si no existe un elemento menor
que cualquier elemento anterior del array/lista.
Este es el orden por defecto

! El orden es descendente si no existe un

elemento mayor

! Un array/lista de Object no se puede

ordenar
" Object no define métodos para determinar cuando

un objeto es mayor/menor que otro

Algoritmos y Estructuras de datos DIT-UPM

7

El interfaz Comparable

!  El interfaz java.lang.Comparable incluye el

método:
public int compareTo(Object that)
"  Este método devuelve:

#  < 0 si el objeto es menor que that
#  0 si el objeto y that son iguales
#  >0 si el objeto es mayor que that

!  Clases que son comparables, y pueden formar parte
de arrays/listas ordenables, implementan el interface
Comparable

class MiClase implements Comparable {
public int compareTo(Object that) {...}}
!  Algunas clases que lo implementan: Date, Integer,

Boolean, String

Algoritmos y Estructuras de datos DIT-UPM

8

Garantías de las implementaciones
de Comparable

! Hay que garantizar:

" x.compareTo(y) y y.compareTo(x) o devuelven los
dos 0, o uno devuelve positivo y el otro negativo
" x.compareTo(y) levanta excepción si y solo si también

la levanta y.compareTo(x)

" La regla es transitiva:

#  (x.compareTo(y)>0 && y.compareTo(z)>0) implica

x.compareTo(z)>0

#  Si x.compareTo(y)==0, entonces x.compareTo(z) y

y.compareTo(z) devuelven valores del mismo signo

! Consistencia entre compareTo y equals

" x.compareTo(y)==0 implica x.equals(y)

Algoritmos y Estructuras de datos DIT-UPM

9

Búsqueda binaria

! Para saber si un elemento en a[izq..der] es



igual a buscado (donde a ésta ordenado):

int i = izq; int d = der;
while (i <= d) {
int m=(i + d)/2;
int cmp =

int i = izq; int d = der;
while (i <= d) {
int m=(i + d)/2;
if (buscado == a[m]) return m;
else if (buscado < a[m]) d = m–1;
else /*buscado > a[m]*/ i = m+1;
}
return NINGUNO;


buscado.compareTo(a[m]);

if (cmp == 0) return m;
else if (cmp < 0) d = m–1;
else /* (cmp > 0) */ i = m+1;
}
return NINGUNO;


10

Algoritmos y Estructuras de datos DIT-UPM

Ejemplo búsqueda binaria

Buscar 36 en el siguiente array
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 7 10 13 13 15 19 19 23 28 28 32 32 37 41
46
1. (0+15)/2=7; a[7]=19;

36 > 19; buscar en 8..15

a

2. (8+15)/2=11; a[11]=32;

36 > 32; buscar en 12..15

3. (12+15)/2=13; a[13]=37;

36 < 37; buscar en 12..12

4. (12+12)/2=12; a[12]=32;

36 > 32; buscar en 13..12. Pero 13 > 12 -> 36, no encontrado
11

Algoritmos y Estructuras de datos DIT-UPM

Búsqueda binaria es O(log n)

! El algoritmo va partiendo el subarray en 2 y
sigue buscando en la mitad correspondiente

! Repetimos la partición en 2 hasta que

encontramos el valor o llegamos a un subarray
de tamaño 1

! Si empezamos con un array de tamaño n,

repetimos el bucle log2n veces

! La complejidad es O(log n)

" Para un array de tamaño 1000, el orden de la

búsqueda binaria es 100 veces el de la búsqueda
lineal (210 ~= 1000)

Algoritmos y Estructuras de datos DIT-UPM

12

Búsquedas en Java

!  Las clases Arrays y Collections incluyen los métodos

(sobrecargados):
"  sort: ordena el array/lista con un algoritmo de orden n*log n
"  binarySearch: es una implementación de búsqueda binaria (O(log n))

pero los elementos deben estar ordenador con sort

#  Collections: si la implementación de la lista no soporta acceso aleatorio hay

que buscar la posición media mediante bucle y el algoritmo es O(n)

!  O(log n) O(n) O(n log n)
!  Si hacemos 1 búsqueda:

"  Compensa ordenar y buscar binario o es mejor una búsqueda lineal?

!  Y si hacemos n búsquedas?
!  Varios interfaces (por ejemplo List, Set) y clases (por ejemplo

ArrayList, LinkedHashSet) incluyen el método contains; cada uno
tiene implementaciones diferentes

Algoritmos y Estructuras de datos DIT-UPM

13

Búsqueda lineal vs binaria

!  La búsqueda lineal tiene una complejidad lineal
!  La búsqueda binaria tiene una complejidad

logarítmica

!  Para grandes arrays/listas la búsqueda binaria es

mas eficiente
"  Pero primero tenemos que ordenar el array/lista
"  Insertar en array no ordenado es O(1) y en ordenado O(n)

(hay que hacer hueco). En la lista depende de
implementación

!  El análisis debe decidir cuando compensa ordenar
las colecciones e insertar ordenado, y que algoritmos
de búsqueda debemos utilizar

Algoritmos y Estructuras de datos DIT-UPM

14

Arboles de búsqueda binarios

!  Los árboles de búsqueda binarios (BST, Binary Search Tree)

buscan combinar:
"  Flexibilidad de la inserción

de las listas enlazadas

"  Eficiencia de la búsqueda en

arrays ordenados

7

6

8

!  Un BST es un árbol en el que los nodos tienen una clave

Comparable y dos enlaces (izquierda y derecha)
a otros nodos, y
"  todos los nodos del subárbol al que

referencia izquierda tienen una clave menor

"  Todos los nodos del subárbol de derecha

izquierda

D

derecha

izquierda

B

E
derecha

tienen clave mayor
!  Ejemplo aplicación:

tablas símbolos compiladores

Algoritmos y Estructuras de datos DIT-UPM

Asubárbol
C

A

B

C D E
15

Búsqueda en BST

!  Un algoritmo recursivo de búsqueda en BST

recursivo-> buscar en el subárbol izquierdo

1.  Si el árbol está vacío falla la búsqueda
2.  Si la clave del nodo es la buscada -> encontrado
3.  Si la clave es menor que la del nodo
4. 
5.  Si la clave es mayor que la del nodo
6. 



recursivo-> buscar en el subárbol derecho

Buscar T

3. R<S

S

Buscar R

S

5. T>S

E

5. R>E

X

R

2. R=R

A

C

H

M

A

E

X
3. T<X

1. NINGUNO

C

H

R

M

Algoritmos y Estructuras de datos DIT-UPM

16

!  Insertar es parecido a buscar, pero remplazamos el

Insertar en BST

este es el hueco
actualizar el padre

enlace vacío
1.  Si el árbol está vacío
2. 
3. 
4.  Si la clave es menor que la del nodo
5. 
6.  Si la clave es mayor que la del nodo
7. 



recursivo-> buscar en el subárbol izquierdo

recursivo-> buscar en el subárbol derecho

Insertar L

A

S

4. L<S

E

6. L>E

X

R

6. L>H
M

4. L<R
C

H

4. L<M

Algoritmos y Estructuras de datos DIT-UPM

17

1. Vacío
2. Hueco
3. Padre

L

Análisis de algoritmos de BST

!  Los tiempos dependen de la forma de los árboles,
que dependen de cómo evolucionen las inserciones
"  Mejor caso: el árbol tiene menor profundidad. O(log n)
"  Peor caso: mayor profundidad. O(n)

H

C

A

S

A

E

R

X

S

R

E

C

H

X

A

C

E

H

R

S

Mejor Caso

Caso Normal

Peor Caso

Algoritmos y Estructuras de datos DIT-UPM

X

18

Balanceado de BST

!  Objetivo: garantizar una profundidad máxima de

O(log n)

!  Condición ideal para que un árbol esté equilibrado:

"  Número de elementos de izquierda y derecha de cada

subárbol tengan una diferencia máxima de 1

"  Es difícil de mantener (algoritmos complejos de inserción y

borrado)

!  Algunos tipos de árboles BST fijan condiciones mas

flexibles de implementar, que garantizan una
profundidad máxima cercana o igual a log n