Eficiencia de algoritmos PDF

Preview

Summary

Trabajo de investigación sobre la eficiencia y análisis de algoritmos computacionales...

Description

UNIVERSIDAD AUTÓNOMA DE BAJA CALIFORNIA SUR DEPARTAMENTO ACADÉMICO DE SISTEMAS COMPUTACIONALES

“Introducción al análisis de algoritmos”.

Ingeniería en Desarrollo de Software.

Semestre 4.

Estructura de datos 2

La Paz, Baja California Sur

INTRODUCCIÓN

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. Para poder trabajar sobre el análisis de un algoritmo es necesario definir con claridad que es un algoritmo. Es evidente que conviene buscar algoritmos correctos que mantengan tan bajo como sea posible el consumo de recursos, es decir, que sean lo más eficientes posible. Cabe hacer notar que el concepto de eficiencia de un algoritmo es un concepto relativo, esto quiere decir que ante dos algoritmos correctos que resuelven el mismo problema, uno es más eficiente que otro si consume menos recursos. Por tanto, podemos observar que el concepto de eficiencia y en consecuencia el concepto de coste nos permitirá comparar distintos algoritmos entre ellos.

IMPORTANCIA DEL USO ADECUADO DE ALGORITMOS. Un algoritmo es una secuencia de pasos lógicos necesarios para llevar a cabo una tarea específica, como la solución de un problema. [1] Cuando realizamos un programa de computadora, no podemos empezar a escribir sentencias (órdenes, instrucciones) sin antes planificar (y más cuan mayor y difícil sea el problema a resolver) y qué es lo que va a hacer exactamente el programa y cómo va a hacerlo, y luego traducir este algoritmo a instrucciones. El siguiente ejemplo compara dos funciones las cuales realizan la misma tarea (calcular la suma de los primeros n enteros), pero no están escritos de la misma manera:

Ilustración 1 Función 1 [3]

Ilustración 2 Función 2 [3]

La pregunta planteada es, ¿Cuál de los dos es mejor?, ambas funciones resuelven el mismo problema, aunque la legibilidad es un punto importante al momento de diseñar un algoritmo tanto para quién lo diseña como para los que trabajan con él, la cantidad de recursos consumidos es un factor determinante, sea la cantidad de

memoria que necesite para resolver un problema o el tiempo invertido, un buen desarrollador siempre buscará la manera en que el algoritmo sea el más eficiente en el aspecto de tiempo y memoria cuidando el apartado de la estructura y legibilidad del mismo. CONSIDERACIONES DE EFICIENCIA

La eficiencia de un algoritmo es la propiedad mediante la cual un algoritmo debe alcanzar la solución al problema en el tiempo más corto posible o utilizando la cantidad más pequeña posible de recursos físicos y que sea compatible con su exactitud o corrección. Un buen programador buscará el algoritmo más eficiente dentro del conjunto de aquellos que resuelven con exactitud un problema dado. [4] Dado el siguiente ejemplo:

Ilustración 3 Algoritmo de búsqueda secuencial

¿De qué dependerá la eficiencia del algoritmo?

1. Dependencia con el tamaño de la entrada: No se tarda lo mismo en buscar en un vector de 10 elementos que buscar en uno de 1.000.000 2. Dependencia de valores de la entrada: Aunque fijemos el tamaño del vector, no se tarda lo mismo en buscar un valor que está en la primera posición que otro que no esté en el vector. 3. Decencia del procesador: Aunque fijemos el tamaño y los valores concretos del vector y el valor buscado, el algoritmo tardará tiempos distintos en ordenadores diferentes. [5] Se tienen contemplados distintos tipos de análisis de eficiencia algorítmica: 1. Mejor caso (condiciones óptimas):

2. Caso promedio (difícil de caracterizar en la práctica):

3. Peor caso (pero escenario posible):

[6]

MEDICIÓN DEL TIEMPO DE EJECUCIÓN El tiempo de ejecución es el período en el que un programa es ejecutado por el sistema operativo. El período comienza cuando el programa es llevado a la memoria primaria y comienzan a ejecutarse sus instrucciones. El período finaliza cuando el programa envía la señal de término (normal o anormal) al sistema operativo. [8] Medir de forma precisa este tiempo no es una tarea trivial, y los resultados pueden variar sensiblemente de un ordenador a otro. La cantidad de factores que pueden influir en el tiempo de ejecución es muy larga:  

Algoritmo usado. Sistema operativo.

 

Velocidad del procesador, número de procesadores y conjunto de instrucciones que entiende. Cantidad de memoria RAM, y caché, y velocidad de cada una.

Un mismo algoritmo se puede llamar con distintos datos de entrada. El objetivo es estudiar el tiempo de ejecución como función del “tamaño” de los datos de entrada. Para ello se usarán dos técnicas:  

Medir tiempos de ejecución de los programas con datos de entrada de distintos tamaños. Contar el número de operaciones que realiza el programa.

Ejemplos: Dato de entrada: 500.

Ilustración 4 Ejemplo 1

El apartado CPU time es la cantidad de tiempo que la CPU ha invertido al cálculo y Wall time el tiempo invertido por el reloj entre el comienzo y el final del cálculo. Dato de entrada: 1000.

Ilustración 5 Ejemplo 2

Al ingresar un valor mucho más grande, el tiempo de ejecución se incrementa significativamente, ya que la CPU requiere de más ciclos para ejecutar el algoritmo. [7] NOTACIÓN ASINTÓTICA

En computación, la notación asintótica nos permite representar la complejidad, y por ende la eficiencia, de un algoritmo, de tal manera que podemos proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada (input).

Desde este punto de vista, el algoritmo más eficiente posible sería aquel en el que el número de operaciones llevadas a cabo no varíe según crezca la entrada. Esto es lo que sería una función constante. Por ejemplo:

En las funciones anteriores, el número de operaciones realizados es independiente del tamaño de la entrada (el trabajo realizado es el mismo para n = 1 que para n = 1000). Por esto, decimos que son constantes, y su Big O (O Grande) es O(1). En las funciones anteriores, el número de operaciones realizados es independiente del tamaño de la entrada (el trabajo realizado es el mismo para n = 1 que para n = 1000). Por esto, decimos que son constantes, y su Big O (O Grande) es O(1).

En la función de arriba, el número de operaciones va a ir aumentando según aumente el valor de n. En este caso el aumento va a ser lineal, ya que el bloque

principal de nuestro código se va a ejecutar una vez para cada iteración, y así n = 1 resulta en 1 operación y n = 1000 resulta en 1000 operaciones. Por ello, en notación asintótica diríamos que nuestro algoritmo tiene una O grande (Big O) de O(n). Si tuviéramos un algoritmo que hace la misma iteración dos veces (una después de otra), diríamos que es O(2n), y si la segunda iteración estuviera anidada entonces sería O(n^2) (n al cuadrado). Hasta ahora sólo hemos mencionado O(1) y O(n), pero de forma común veremos eficiencias de O(log(n)), O(n * log(n)) en algoritmos eficientes y O(n^2) (n al cuadrado) o mayores en algoritmos más complejos. Ejemplo 2:

La función de arriba tiene una O Grande de O(n), es lineal, pero como siempre, existen muchas formas de solucionar el problema. En este caso hay una solución matemática que nos permite implementar la misma lógica de una forma más eficiente:

La nueva implementación de sumaDeEnteros() produce exactamente los mismos resultados que la anterior, pero tiene una O Grande de O(1), es constante, ya que

el número de operaciones es siempre 1, independientemente del valor de n; es mucho más eficiente.

Para poder “visualizar” cómo afecta el tamaño de la entrada al número de operaciones se ha creado una “gráfica interactiva” donde pueden comparar las curvas que producen las diferentes O Grandes (constante, lineal, logarítmica, polinomial, exponencial) al “plotear” n y las operaciones resultantes. [8]

CONCLUSIÓN

El análisis de algoritmos es una parte importante de la teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. La característica básica que debe tener un algoritmo es que sea correcto, es decir, que produzca el resultado deseado en tiempo finito. A demás puede interesarnos que sea claro, que esté bien estructurado, que sea fácil de usar, que sea fácil de implementar y que sea eficiente.

BIBLIOGRAFÍA

[1] http://correo.uan.edu.mx/~iavalos/FP/FP1.html [2] https://www.importancia.org/algoritmos.php [3] http://interactivepython.org/runestone/static/pythoned/AlgorithmAnalysis/QueEsAn alisisDeAlgoritmos.html [4] http://miinformatica360.blogspot.com/2013/10/eficiencia-de-un-algoritmo.html [5] https://www.infor.uva.es/~cvaca/asigs/doceda/tema1.pdf [6] https://www.cs.upc.edu/~duch/home/duch/analisis.pdf [7] http://verso.mat.uam.es/~pablo.angulo/doc/laboratorio/b2s2.html [8] https://medium.com/laboratoria-developers/algoritmos-y-notación-asintótica817a666ca444...