Estructura de Datos - Introducción

Estructuras de datos y algoritmos

UNIVERSIDAD
DE CANTABRIA

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

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

1.1 Estructuras de datos abstractas

UNIVERSIDAD
DE CANTABRIA

Unaestructura 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 seimplementa
• 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

UNIVERSIDAD
DE CANTABRIA

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 diversasaplicaciones
Parte
Pública

Objeto
Operación 1
Operación 2

Estado

Parte
Privada

Operación n

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

UNIVERSIDAD
DE CANTABRIA

Entre loscriterios 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
saber midiéndolo
• predicción del ritmo de crecimiento del tiempo de ejecución con
respecto al tamañodel 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
2n

UNIVERSIDAD
DE CANTABRIA

n3/2
5n2

3000

T(n)

100n

2000

1000

26

21

16

11

6

1

0
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.)DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

Función

n=25

n=50

100n

2.5 seg

5.0 seg

5n2

3.12 seg

12.5 seg

n3/2

7.81 seg

62.5 seg

2n

33554.43 seg

35677 años

© Michael González Harbour
23/sept/09

UNIVERSIDAD
DE CANTABRIA

7

La notación O(n)

UNIVERSIDAD
DE CANTABRIA

El tiempo de ejecución depende no sólo de la cantidad de datos (n)
sino también de cuáles son los datos; porello 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

© MichaelGonzález Harbour
23/sept/09

8

La notación O(n) (cont.)

UNIVERSIDAD
DE CANTABRIA

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
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)...