Algoritmos Y Estructuras De Datos UNLP

Apuntes de Algoritmos y Estructuras de Datos
Programaci´on III
Facultad de Inform´atica - UNLP
Alejandro Santos
ale@ralo.com.ar
Curso 2013
(actualizado 29 de julio de 2013)

Prog. III

2

´Indice general
1. Tiempo de Ejecuci´
on
1.1. Tiempo de Ejecuci´on . . . . . . . . . . . . . . . .
1.2. An´alisis Asint´otico BigOh . . . . . . . . . . . . .
1.2.1. Por definici´on . . . . . . . . . . . . . .. .
1.2.2. Ejemplo 1, por definici´on Big-Oh . . . . .
1.2.3. Por regla de los polinomios . . . . . . . . .
1.2.4. Por regla de la suma . . . . . . . . . . . .
1.2.5. Otras reglas . . . . . . . . . . . . . . . . .
1.2.6. Ejemplo 2, por definici´on Big-Oh . . . . .
1.2.7. Ejemplo 3, por definici´on Big-Oh en partes
1.2.8. Ejemplo 4, por definici´on. . . . . . . . . .
1.3. An´alisis de Algoritmos yRecurrencias . . . . . . .
1.3.1. Expresi´on constante . . . . . . . . . . . .
1.3.2. Grupo de constantes . . . . . . . . . . . .
1.3.3. Secuencias . . . . . . . . . . . . . . . . . .
1.3.4. Condicionales . . . . . . . . . . . . . . . .
1.3.5. for y while . . . . . . . . . . . . . . . . . .
1.3.6. for y while, ejemplo . . . . . . . . . . . . .
1.3.7. Llamadas recursivas . . . . . . . . . . . .1.3.8. Ejemplo 5, iterativo . . . . . . . . . . . . .
1.3.9. Ejemplo 6, recursivo . . . . . . . . . . . .
1.3.10. Ejemplo 7, recursivo . . . . . . . . . . . .
1.3.11. Ejemplo 8, Ejercicio 12.4 . . . . . . . . . .
1.4. Otros ejemplos . . . . . . . . . . . . . . . . . . .
1.4.1. Ejemplo 9 . . . . . . . . . . . . . . . . . .
Planteo de la recurrencia . . . . . . . . . .
Demostraci´on del orden O(f (n)). . . . .
1.4.2. Ejemplo 10 . . . . . . . . . . . . . . . . .
Antes de empezar . . . . . . . . . . . . . .
Ejercicio . . . . . . . . . . . . . . . . . . .
3

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

7
8
8
9
9
10
10
11
11
12
13
15
15
15
15
15
15
15
17
17
18
19
21
23
23
23
25
26
26
27

´INDICE GENERAL

Prog. III

Demostraci´on del orden O(f (n)) . . . . . . . . . . . . 29
1.5. Identidades de sumatorias y logaritmos . . . . .. . . . . . . . 30
2. Listas
2.1. Los Pares del Fara´on . . . . . . . . . . . . . . . . . . . . .
2.1.1. Explicaci´on del problema . . . . . . . . . . . . . . .
2.1.2. Implementaci´on Java . . . . . . . . . . . . . . . . .
2.2. PilaMin . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Explicaci´on del problema . . . . . . . . . . . . . . .
2.2.2. Implementaci´on Java - Versi´on conLista Enlazada .
2.2.3. PilaMin, menor elemento en tiempo O(1) . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

31
32
32
33
34
34
35
35

´
3. Arboles
binarios y Generales
3.1. Evaluar a´rbol de expresi´on . . . . . . . . . . . . . . .
3.1.1. Explicaci´on del problema . . . . . . . . . . . .
3.1.2. Implementaci´on Java . . . . . . . . . . . . . .
3.2. M´ınimo del Nivel . . . . . . . . . . . . . . . . . . ..
3.2.1. Explicaci´on del problema . . . . . . . . . . . .
3.2.2. Implementaci´on Java - Recursivo con Integer
3.2.3. Implementaci´on Java - Recursivo con int . . .
3.2.4. Implementaci´on Java - Iterativo . . . . . . . .
3.3. Trayectoria Pesada . . . . . . . . . . . . . . . . . . .
3.3.1. Forma de encarar el ejercicio . . . . . . . . . .
3.3.2. Recorrido del a´rbol . . . . . . . . . . . . . . .3.3.3. Procesamiento de los nodos . . . . . . . . . .
3.3.4. Almacenamiento del resultado . . . . . . . . .
3.3.5. Detalles de implementaci´on . . . . . . . . . .
Modularizaci´on . . . . . . . . . . . . . . . . .
esHoja() . . . . . . . . . . . . . . . . . . . .
public y private . . . . . . . . . . . . . . .
Clases abstractas . . . . . . . . . . . . . . . .
3.3.6. Errores comunes en las entregas ....