Descargar

Análisis de algoritmos

Enviado por Pablo Turmero


Partes: 1, 2

    edu.red

    1 Análisis de Algoritmos

    Metodologías para el análisis de algoritmos

    Notación asintótica

    Elementos matemáticos

    Otras técnicas de análisis

    edu.red

    2 Metodologías para el análisis de algoritmos La complejidad de un algoritmo estudia los recursos necesarios (tiempo y memoria) que requiere un algoritmo. El tiempo de ejecución de un algoritmo o es prioritario cuando se analiza un algoritmo. El tiempo de ejecución de un algoritmo o estructura de datos depende de varios factores relativos al hardware (procesador, reloj, memoria, disco, etc) y el software (sistema operativo, lenguaje, compilador, etc.).

    edu.red

    3 Metodologías para el análisis de algoritmos Medida del tiempo de ejecución: experimentación. Escribir un programa que implemente el algoritmo. Ejecutar el programa con un conjunto de datos que varían en tamaño y composición (peor caso, mejor caso, caso promedio) . Usar un método como System.currentTimeMillis() para obtener una medida precisa del tiempo de ejecución.

    edu.red

    4 Metodologías para el análisis de algoritmos Medida del tiempo en Java: experimentación.

    long startTime = System.currentTimeMillis(); // retorna el tiempo en miliseconds desde 1/1/1970 GMT

    // código a ser medido

    long elapsedTime = System.currentTimeMillis() – startTime;

    edu.red

    5 Metodologías para el análisis de algoritmos Medida del tiempo en Java: experimentación.

    edu.red

    6 Metodologías para el análisis de algoritmos Medida del tiempo en Java (más preciso):

    long startTime = System.currentTimeMillis(); long counter; do { counter++; hacerAlgo ( ); } while (System.currentTimeMillis() – startTime < 1000), long elapsedTime = (System.currentTimeMillis() – startTime) / counter;

    edu.red

    7 Metodologías para el análisis de algoritmos Interesa hallar la dependencia del tiempo de ejecución en función del tamaño de la entrada. Un método para estudiar el tiempo de ejecución es la experimentación, que tiene limitaciones: Los experimentos se pueden hacer sobre un conjunto limitado de entradas de prueba. Es necesario realizar los experimentos con el mismo hardware y software. Es necesario implementar y ejecutar el algoritmo.

    edu.red

    8 Metodologías para el análisis de algoritmos Adicionalmente a la experimentación conviene disponer de un enfoque analítico que: Tome en consideración todas las posibles entradas. Permita evaluar la eficiencia de dos algoritmos de forma independiente del hardware y software. Se pueda realizar estudiando una representación de alto nivel del algoritmo sin necesidad de implementarlo.

    edu.red

    9 Pseudocódigo Pseudocódigo es una descripción de un algoritmo más estructurada que la verbal pero menos formal que la de un lenguaje de programación. Ejemplo: hallar el elemento mayor de un array. Algorithm arrayMax(A, n): Input: Un array A que almacena n enteros. Output: El máximo elemento en A. currentMax ? A[0] for i? 1 to n -1 do if currentMax < A[i] then currentMax ? A[i] return currentMax Pseudocódigo es la notación preferida para describir algoritmos.

    edu.red

    10 Qué es pseudocódigo Una mezcla de lenguaje natural y conceptos de programación de lato nivel que describen las proncipales ideas que están en una implementación genérica de una estructura de datos o algoritmo. -Expresiones: usa símbolos matemáticos standard para describir expresiones numéricas y booleanas -usa ? for assignment ("=" in Java) -usa = for the equality relationship ("==" in Java) -Declaración de métodos: -Algorithm nombre(param1, param2) -Bloques Programación: – decision structures: if … then … [else … ] – while-loops: while … do – repeat-loops: repeat … until … – for-loop: for … do – array indexing: A[i] -Métodos: – llamadas: object method(args) – returns: return value

    edu.red

    11 Análisis de algoritmos Operaciones Primitivas: se pueden identificar en el pseudocódigo instrucciones de bajo nivel independientes del lenguaje de programación. Ejemplos: llamar un método y retornar de un método operaciones aritméticas (e.g. suma) comparación de dos números, etc. Inspeccionando el pseudocódigo se puede contar el número de operaciones primitivas ejecutadas por un algoritmo.

    edu.red

    12 Ejemplo de conteo Algorithm arrayMax(A, n): Input: Un array A que almacena n enteros. Output: El máximo elemento en A. currentMax ? A[0] for i? 1 to n -1 do if currentMax < A[i] then currentMax ? A[i]

    return currentMax

    t(n) = 2 + 1 + n +4(n-1) + 1 = 5n (mínimo) = 2 + 1 + n +6(n-1) + 1 = 7n – 2 (máximo)

    2 1 n 4(n-1) | 6(n-1) 1

    Partes: 1, 2
    Página siguiente