Estructura de Datos - Introducción
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)...
Regístrate para leer el documento completo.