Estructuras De Datos

Introducción
Técnicas Fundamentales de análisis y diseño de

algoritmos.

ESTRUCTURAS DE DATOS
1

Introducción
 Algoritmo:

Conjunto de reglas para resolver un problema. Su ejecución requiere unos recursos.
 Un algoritmo es mejor cuantos menos recursos

consuma, su facilidad de programarlo, corto, fácil de entender, robusto, etc.
 Eficiencia: Relación entre los recursosconsumidos y los productos conseguidos.
ESTRUCTURAS DE DATOS M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

2

Introducción
Recursos consumidos:
   

Tiempo de ejecución. Memoria principal: Entradas/salidas a disco. Comunicaciones, procesadores, etc.

Lo que se consigue:  Resolver un problema de forma exacta, forma aproximada o algunos casos.

ESTRUCTURAS DE DATOS

M.C. BLANCA IDALIAMARTÍNEZ CAVAZOS

3

Introducción
Recursos consumidos: Ejemplo. ¿Cuántos recursos de tiempo y memoria consume el siguiente algoritmo sencillo? i:= 0 a[n+1]:= x repetir i:= i + 1 hasta a[i] = x Respuesta: Depende. ¿De qué depende? De lo que valga n y x, de lo que haya en a, de los tipos de datos, de la máquina...

ESTRUCTURAS DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

4

IntroducciónEn general los recursos dependen de: Factores externos.  El ordenador donde lo ejecutemos: 286, Pentium III, Cray,...  El lenguaje de programación y el compilador usado.  La implementación que haga el programador del algoritmo. En particular, de las estructuras de datos utilizadas.  Tamaño de los datos de entrada.

ESTRUCTURAS DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

5Introducción
Ejemplo. Calcular la media de una matriz de NxM. Contenido de los datos de entrada.  Mejor caso. El contenido favorece una rápida ejecución.  Peor caso. La ejecución más lenta posible.  Caso promedio. Media de todos los posibles contenidos. Los factores externos no aportan información sobre el algoritmo.  Conclusión: Estudiar la variación del tiempo y la memoria necesitada por unalgoritmo respecto al tamaño de la entrada y a los posibles casos, de forma aproximada (y parametrizada) no aportan información sobre el algoritmo.
ESTRUCTURAS DE DATOS M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

6

Introducción
 Normalmente usaremos la notación T(N)=..., pero ¿qué significa

T(N)?  Tiempo de ejecución en segundos. T(N) = bN + c. Suponiendo que b y c son constantes, con los segundosque tardan las operaciones básicas correspondientes. Instrucciones ejecutadas por el algoritmo. T(N) = 2N + 4. ¿Tardarán todas lo mismo? Ejecuciones del bucle principal. T(N) = N+1. ¿Cuánto tiempo, cuántas instrucciones,...? Sabemos que cada ejecución lleva un tiempo constante, luego se diferencia en una constante con los anteriores.

ESTRUCTURAS DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS7

Introducción
Asignación de tiempos, para el conteo de instrucciones. Algunas reglas básicas. Operaciones básicas (+, -, *, :=,...): Una unidad de tiempo, o alguna constante. Operaciones de entrada salida: Otra unidad de tiempo, o una constante diferente. Bucles FOR: Se pueden expresar como una sumatoria, con los límites del FOR. IF y CASE: Estudiar lo que puede ocurrir. Mejor caso y peorcaso según la condición. ¿Se puede predecir cuándo se cumplirán las condiciones? Llamadas a procedimientos: Calcular primero los procedimientos que no llaman a otros. Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir. ¿Existe una cota inferior y superior del número de ejecuciones? ¿Se puede convertir en un FOR?
ESTRUCTURAS DE DATOS M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

8

Técnicasfundamentales de análisis y diseño de algoritmos
 El rendimiento o complejidad está ligado únicamente al algoritmo. En ningún momento con la velocidad del computador o con las facilidades de eficiencia que presenta un lenguaje de programación, ni con el estilo hábil del programador.
 Para calcular este rendimiento se tiene en cuenta dos pasos principales:

1. Caracterizar las operaciones básicas...