PDF de programación - Estructuras de datos y algoritmos 1. Introducción

Estructuras de datos y algoritmos
1. Introducción
2. Estructuras de datos lineales
3. Estructuras de datos jerárquicas
4. Grafos y caminos
5. Implementación de listas, colas, y pilas
6. Implementación de mapas, árboles, y grafos

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

1

UNIVERSIDAD
DE CANTABRIA

1. Introducción
• 1.1 Estructuras de datos abstractas
• 1.2 Eficiencia de las estructuras de datos
• 1.3 Interfaces y herencia múltiple
• 1.4 Estructuras de datos genéricas
• 1.5 Colecciones
• 1.6 Iteradores
• 1.7 Relaciones de igualdad y orden

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

2

UNIVERSIDAD
DE CANTABRIA

1.1 Estructuras de datos abstractas
Una estructura o tipo de datos abstracto (ADT) es una clase o
módulo de programa que contiene:
• datos privados, con una determinada estructura
• un conjunto de métodos públicos para manejar esos datos
El conjunto de operaciones permite el uso de la estructura de
datos sin conocer los detalles de su implementación
• los programas que usan la clase son independientes de la forma

en la que éste se implementa

• no es necesario conocer los detalles internos del tipo de datos

ni de su implementación

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

3

Encapsulamiento
Se dice que la clase encapsula el tipo de datos junto a sus
operaciones, ocultando los detalles internos
• consiguen la reutilización de código
• para muy diversas aplicaciones

UNIVERSIDAD
DE CANTABRIA

Parte
Pública

Operación 1

Operación 2

Operación n

Objeto

Estado

Parte
Privada

Por ejemplo, las listas o colas que estudiamos el año pasado
• aunque necesitamos saber la eficiencia de los métodos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

4

1.2 Eficiencia de las estructuras de
datos
Entre los criterios a tener en cuenta al diseñar o elegir un algoritmo
están su complejidad, y su tiempo de ejecución
El tiempo de ejecución depende de factores variados y, muy en
particular, del tamaño del problema
El tiempo de ejecución puede ser:
• exacto: es muy difícil de predecir; normalmente sólo se puede

UNIVERSIDAD
DE CANTABRIA

saber midiéndolo

• predicción del ritmo de crecimiento del tiempo de ejecución con

respecto al tamaño del problema

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

5

La “tiranía” del ritmo de crecimiento

UNIVERSIDAD
DE CANTABRIA

3000

2000

)
n
(
T

1000

0

1

2n

n3/2

5n2

100n

6

1
1

6
1

1
2

6
2

n

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

6

La “tiranía” del ritmo de crecimiento
(cont.)

UNIVERSIDAD
DE CANTABRIA

Función

100n
5n2
n3/2
2n

n=25
2.5 seg
3.12 seg
7.81 seg

n=50
5.0 seg
12.5 seg
62.5 seg

33554.43 seg

35677 años

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

7

UNIVERSIDAD
DE CANTABRIA

La notación O(n)
El tiempo de ejecución depende no sólo de la cantidad de datos (n)
sino también de cuáles son los datos; por ello distinguimos:
• tiempo de peor caso: T(n)
• tiempo promedio: Tavg(n)
Para expresar los ritmos de crecimiento se suele usar la notación
O(n):
• decimos que T(n) es O(f(n)) si existen constantes c y n0 tales que
T(n)≤c⋅f(n) para todo n≥n0

La notación O(n) muestra una cota superior al ritmo de crecimiento
de un algoritmo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

8

La notación O(n) (cont.)
El tiempo en la notación O(n) es relativo
• Las unidades de T(n) son inespecíficas
Por ejemplo, la función T(n) = 3n3+2n2 es O(n3).
• Basta hacer c=5 y no=0 para comprobarlo,

3n3+2n2 ≤ 5n3

UNIVERSIDAD
DE CANTABRIA

En definitiva, cuando decimos que T(n) es O(f(n)), esto significa
que f(n) es el límite de la velocidad de crecimiento de T(n)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

9

La notación Ω(n)
También se puede expresar un límite inferior al ritmo de
crecimiento de T(n) mediante la notación Ω(n):
• decimos que T(n) es Ω(g(n)) si existe una constante c tal que

T(n)≥c.g(n) para un número infinito de valores de n

UNIVERSIDAD
DE CANTABRIA

Por ejemplo, T(n) = n3 + 2n2 es Ω(n3)
• Basta probar para c=1 y n>0.
Recordar siempre que tanto O(n) como Ω(n) son medidas relativas,
no absolutas
• Por ejemplo, supongamos dos algoritmos cuyos tiempos de
ejecución son O(n2) y O(n3)
• ¿Qué ocurre si las constantes son 100n2 y 5n3?

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

10

UNIVERSIDAD
DE CANTABRIA

Cálculo del tiempo de ejecución de un
programa
Regla de las sumas:
• si T1(n) es O(f(n)) y T2(n) es O(g(n)), entonces
• T1(n)+T2(n) es O(max(f(n),g(n)))
Es decir, que la suma de los tiempos de ejecución de dos
algoritmos tiene un ritmo de crecimiento igual al del máximo de los
dos
Por ejemplo, para tiempos polinómicos T(n)=anp+bnp-1+...
• entonces T(n) es O(np)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

11

UNIVERSIDAD
DE CANTABRIA

Cálculo del tiempo de ejecución de un
programa (cont.)
Regla de los productos:
• si T1(n) es O(f(n)) y T2(n) es O(g(n)), entonces
• T1(n)⋅T2(n) es O((f(n)⋅g(n)))
Es decir, que el producto de los tiempos de ejecución de dos
algoritmos (p.e. cuando uno está anidado en el otro), tiene un ritmo
de crecimiento igual al producto de los dos
Por ejemplo si T(n) es O(c⋅f(n)) entonces también es O(f(n)), ya que
c es O(1)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

12

UNIVERSIDAD
DE CANTABRIA

Ritmos de crecimiento más habituales
1. O(1), o constante
2. O(log(n)), o logarítmico
3. O(n), o lineal
4. O(n⋅log(n))
5. O(n2), o cuadrático
6. O(nx), o polinómico
7. O(2n), o exponencial

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

13

.Ritmos de crecimiento más habituales

UNIVERSIDAD
DE CANTABRIA

n
128
256
512
1024
2048
4096
8192
16384
32768

1
1
1
1
1
1
1
1
1
1

log(n)

7
8
9
10
11
12
13
14
15

n⋅log(n)

896
2048
4608
10240
22528
49152
106496
229376
491520

n2

16384
65536
262144
1048576
4194304
16777216
67108864
268435456
1073741824

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

14

Pistas para el análisis
Instrucciones simples (asignación y op. aritméticas): O(1)
Secuencia de instrucciones simples: O(max(1,1,1)) = O(1)
Instrucción condicional:
• si es un “if” simple y no se conoce el valor de la condición, se

supone que la parte condicional se ejecuta siempre

UNIVERSIDAD
DE CANTABRIA

• si es un “if” con parte “else” y no se conoce el valor de la

condición, se elige la que más tarde de las dos partes

Bucle: número de veces, por lo que tarden sus instrucciones
Procedimientos recursivos: número de veces que se llama a sí
mismo, por lo que tarda cada vez

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

15

Ejemplo de análisis
Analizar el tiempo de ejecución del siguiente algoritmo:

UNIVERSIDAD
DE CANTABRIA

método Burbuja (entero[1..n] A) es
var entero temporal;

fvar
(1)
(2)
(3)

para i desde 1 hasta n-1 hacer

para j desde n hasta i+1 hacer


si A(j-1) > A(j) entonces

(4)
(5)
(6)

// intercambia A(j-1) y A(j)
temporal := A(j-1);
A(j-1) := A(j);
A(j) := temporal;

fsi;
fpara;

fpara;

fmétodo;

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

16

dimensión de entrada
-

(4), (5) y (6) son O(1) y por la regla de las sumas, la secuencia es
O(max(1,1,1))=O(1)

Ejemplo (cont.)
N es el nº de elementos a ordenar. Vamos a analizar el programa
desde el interior hacia el exterior
• Cada instrucción de asignación es O(1), independiente de la

UNIVERSIDAD
DE CANTABRIA

• Si suponemos el peor caso en el “if”, por la regla de las sumas

el grupo de instrucciones (3)-(6) toma un tiempo O(1)

• El lazo que comienza en la línea (2) y abarca hasta la línea (6)
tiene un cuerpo que toma un tiempo de la forma O(1) en cada
iteración, y como toma n-i iteraciones, el tiempo gastado en ese
lazo es O((n-i)⋅1) que es O(n-i).

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

17

Ejemplo (cont.)
• El último lazo se ejecuta n-1 veces, de forma que el tiempo total

UNIVERSIDAD
DE CANTABRIA

de ejecución esta limitado superiormente por:

n
1–
∑
1=

i

n
i–(

)

=

1
---n n
2

1–(

)

=

n2
-----
2

n
---–
2

• que es O(n2)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

18

Ejemplo de análisis recursivo

UNIVERSIDAD
DE CANTABRIA

método Factorial (Entero n) retorna Entero es
comienzo
(1)
(2)

if n <= 1 entonces

retorna 1;

si no

(3)

retorna n*Factorial(n-1);

fin if;

fin Factorial;
La función se llama a sí misma n veces, y cada ejecución es O(1),
luego en definitiva factorial es O(n)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

19

1.3 Interfaces y Herencia Múltiple
En el curso pasado hablamos de la extensión de clases por
herencia:

UNIVERSIDAD
DE CANTABRIA

Vehiculo

Ser Vivo

Coche

Barco

Persona

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

20

Herencia múltiple
Podemos imaginar que podemos querer heredar de varias
jerarquías, con herencia múltiple

UNIVERSIDAD
DE CANTABRIA

Vehiculo

Ente móvil

posicion()

Ser Vivo

Coche

Barco

Persona

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

23/sept/09

21

UNIVERSIDAD
DE CANTABRIA

Herencia Múltiple
La herencia múltiple sin restricciones presenta anomalías
• atributos del mismo nombre
• métodos ig