Algoritmos y estructura de datos

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

Prog. III

2

´
Indice general
1. Tiempo de Ejecuci´n
o
1.1. Tiempo de Ejecuci´n . . . . . . . . . . . . . . . .
o
1.2. An´lisis Asint´tico BigOh . . . . . . . . . . . . .
a
o
1.2.1. Por definici´n .. . . . . . . . . . . . . . .
o
1.2.2. Ejemplo 1, por definici´n Big-Oh . . . . .
o
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´n Big-Oh . . . . .
o
1.2.7. Ejemplo 3, por definici´n Big-Oh en partes
o
1.2.8. Ejemplo 4, por definici´n. . . . . . .. . .
o
1.3. An´lisis de Algoritmos y Recurrencias . . . . . . .
a
1.3.1. Expresi´n constante . . . . . . . . . . . .
o
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 larecurrencia . . . . . . . . . .
Demostraci´n del orden O(f (n)) . . . . .
o
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´n del orden O(f (n)) . . . . . . . . . . . . 29
o
1.5. Identidades de sumatorias y logaritmos . . . . . . . . . . . . . 30
2. Listas
2.1. Los Pares del Fara´n . . . . . . . . . . . .. . . . . . . . .
o
2.1.1. Explicaci´n del problema . . . . . . . . . . . . . . .
o
2.1.2. Implementaci´n Java . . . . . . . . . . . . . . . . .
o
2.2. PilaMin . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Explicaci´n del problema . . . . . . . . . . . . . . .
o
2.2.2. Implementaci´n Java - Versi´n con Lista Enlazada .
o
o
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 arbol de expresi´n . . . . . . . . . . . . . . .
´
o
3.1.1. Explicaci´n del problema . . . . . . . . . . . .
o
3.1.2. Implementaci´n Java . . . . . . . . . . . . . .
o
3.2. M´
ınimo del Nivel . . . . . . . . . . . . . . . . . . . .
3.2.1.Explicaci´n del problema . . . . . . . . . . . .
o
3.2.2. Implementaci´n Java - Recursivo con Integer
o
3.2.3. Implementaci´n Java - Recursivo con int . . .
o
3.2.4. Implementaci´n Java - Iterativo . . . . . . . .
o
3.3. Trayectoria Pesada . . . . . . . . . . . . . . . . . . .
3.3.1. Forma de encarar el ejercicio . . . . . . . . . .
3.3.2. Recorrido del arbol . . . . . . . . . . . . . . .
´...