Análisis de Algoritmos

Ma. Luisa Velasco Ramírez

Algoritmo

• Es un conjunto finito de instrucciones precisas para resolver un problema.

• Su ejecución requiere ciertos recursos.

1.1. Introducción.

ALGORITMO0 ó más entradas

1 ó más salidas

MemoriaComuni-caciones

Características de un algoritmo

• Debe ser Preciso; Esto es, debe especificar sin ambigüedad el orden en que se deben ejecutar las instrucciones.

• Debe estar Definido; Esto es, cada vez que se ejecute bajo las mismas condiciones, la secuencia de ejecución deberá ser la misma proporcionándonos el mismo resultado.

• Debe ser Finito; Esto es, siempre que sea adecuado se realizarán un número finito de instrucciones, en un tiempo finito y requiriendo una cantidad finita de esfuerzo.

•  

Razones para Estudiar los Algoritmos

• Evitar reinventar la rueda.

• Ayuda cuando se desarrollen propios algoritmos.

• Ayuda a entender herramientas que usan algoritmos particulares.

• Útil conocer técnicas empleadas para resolver problemas de determinados tipos.

• Utilizar el algoritmo más eficiente

Eficiencia de Algoritmos

• Desarrollar programas que sean prácticos, en términos de requerimientos de almacenamiento y tiempo de ejecución

• ¿Cómo determinar cuál es

• "el mejor"?

• Estrategia empírica

• Estrategia teórica

• Consiste en determinar matemáticamente la cantidad de recursos (tiempo, espacio) que necesitará el algoritmo en función del tamaño del ejemplar considerado.

• El tamaño de un ejemplar x corresponde formalmente al número de dígitos binarios necesarios para representarlo en la computadora.

• Pero a nivel algorítmico se considerará el tamaño como el número de elementos lógicos contenidos en el ejemplar.

Concepto de Eficiencia

• Un algoritmo es eficiente cuando logra llegar a sus objetivos planteados utilizando la menor cantidad de recursos posibles, es decir, minimizando el uso memoria, de pasos y de esfuerzo humano.

• Un algoritmo es eficaz cuando alcanza el objetivo primordial.

Dos fundamentales:

• Espacio y tiempo.

• · La eficiencia en espacio es una medida de la cantidad de memoria requerida por un programa.

• · La eficiencia en tiempo se mide en términos de la cantidad de tiempo de ejecución del programa.

Recurso Tiempo:

• · Aplicaciones informáticas que trabajan “en tiempo real” requieren que los cálculos se realicen en el menor tiempo posible.

• · Aplicaciones que manejan un gran volumen de información si no se tratan adecuadamente pueden necesitar tiempos impracticables.

Recurso Memoria:

• Las máquinas tienen una memoria limitada

Análisis A Priori y Prueba A Posteriori

• El Análisis A Priori (o teórico) es siempre un estudio teórico previo a la implementación. Puede servir para evitar la implementación, si el algoritmo es poco eficiente.

Esto es interesante porque:

• La predicción del costo del algoritmo puede evitar una implementación posiblemente laboriosa.

• Es aplicable en la etapa de diseño de los algoritmos, constituyendo uno de los factores fundamentales a tener en cuenta.

Prueba A Posteriori

• En la Prueba A Posteriori (experimental o empírica) se recogen estadísticas de tiempo y espacio consumidas por el algoritmo mientras se ejecuta.

• La estrategia empírica consiste en programar los algoritmos y ejecutarlos en una computadora sobre algunos ejemplares de prueba, haciendo medidas para:

• · una máquina concreta,

• · un lenguaje concreto,

• · un compilador concreto y

• · datos concretos

Concepto de Instancia

• Un problema computacional tiene una o más instancias, que son valores particulares para los datos de entrada, sobre los cuales se puede ejecutar el algoritmo para resolver el problema.

• En la teoría de algoritmos es muy frecuente usar el término instancia para

• indicar un caso específico de un problema. Así, por ejemplo, si el problema

• es la multiplicación de 2 enteros positivos una instancia es el par de números

• a multiplicar.

Tamaño de los Datos

• Variable o expresión en función de la cual se intentara medir la complejidad del algoritmo

Se definen entonces las funciones de cantidad de recursos en base al tamaño (o talla) de la entrada.

Suele depender del número de datos del problema.

Este tamaño puede ser:

1. la cantidad de dígitos para un número,

2. la cantidad de elementos para un arreglo,

3. la cantidad de caracteres de una cadena,

4. en problemas de ordenación es el número de elementos a ordenar,

5. en matrices puede ser el número de filas, columnas o elementos totales,

6. en algoritmos recursivos es el número de recursiones o llamadas propias que hace la función.

Análisis Peor Caso, Mejor Caso y Caso Promedio

• Peor caso: indica el mayor tiempo obtenido, teniendo en consideración todas las entradas posibles.

• Mejor caso: indica el menor tiempo obtenido, teniendo en consideración todas las entradas posibles.

• Media: indica el tiempo medio obtenido, considerando todas las entradas posibles.

Ejemplo

• Sea A una lista de n elementos A1 , A2, A3, ... , An. Ordenar significa permutar estos elementos de tal forma que los mismos queden de acuerdo con un orden preestablecido.

• Ascendente A1<=A2<=A3 ..........<=An• Descendente A1>=A2 >=........>=An

• Caso peor: Que el vector esté ordenado en sentido inverso.• Caso mejor: Que el vector esté ordenado.• Caso medio: Cuando el vector esté desordenado

aleatoriamente.

Metas en el diseño de programas de cómputo:

• El diseño de un algoritmo que sea fácil de entender, codificar y depurar (Ingeniería de Software).

• El diseño de un algoritmo que haga uso eficiente de los recursos de la computadora (Análisis y Diseño de algoritmos).

• El análisis de algoritmos permite medir la dificultad inherente de un problema y evaluar la eficiencia de un algoritmo.

Tiempo de Ejecución

• Una medida que suele ser útil conocer es el tiempo de ejecución de un algoritmo en función de N, lo que denominaremos T(N).

• Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.

• S1;

• FOR i:= 1 TO N DO S2 END;

• requiere:

• T(N):= t1 + t2*N

• Siendo t1 el tiempo que lleve ejecutar la serie "S1" de sentencias, y t2 el que lleve la serie "S2".

• Tmin(N) <= T(N) <= Tmax(N)

• Los extremos son habitualmente conocidos como "caso peor" y "caso mejor".

• De este modo, el tiempo de ejecución puede ser definido como una función de la entrada.

• Se definirá T(n) como el tiempo de ejecución de un algoritmo para una entrada de tamaño n.

Concepto de Complejidad

• La complejidad (o costo) de un algoritmo es una medida de la cantidad de recursos (tiempo, memoria) que el algoritmo necesita. La complejidad de un algoritmo se expresa en función del tamaño (o talla) del problema.

»Se expresa como f(n)

• El comportamiento de la función determina la eficiencia. No es única para un algoritmo: depende de los datos.

• Para un mismo tamaño del problema, las distintas presentaciones iníciales de los datos dan lugar a distintas funciones de complejidad.

• Es el caso de una ordenación si los datos están todos inicialmente desordenados, parcialmente ordenados o en orden inverso.

• La complejidad de un algoritmo se expresará en términos de la cantidad de operaciones que realiza.

Cada operación requiere cierta cantidad constante• de tiempo para ser ejecutada, por esta razón si se

cuenta el número de operaciones realizadas por el algoritmo se obtiene una estimación del tiempo que le tomará resolver el problema.

• Dado un algoritmo, se puede determinar que tipos de operaciones utiliza y cuantas veces las ejecuta para una entrada específica.

• Para hacer una estimación de la cantidad de tiempo que tarda un algoritmo en ejecutarse, no es necesario contar el número total de operaciones que realiza.

• Se puede elegir alguna, a la que se identificará como operación básica que observe un comportamiento parecido al del número total

• de operaciones realizadas y que, por lo tanto, será proporcional al tiempo total de ejecución.

• En general, debe procurarse que la operación básica, en la cual se basa el análisis, de alguna forma esté relacionada con el tipo de problema que se intenta resolver, ignorando las asignaciones de valores iníciales y las operaciones sobre variables para control de ciclos (índices).

• Ejemplo 1. El siguiente algoritmo obtiene el producto de los dos valores más grandes contenidos en un arreglo A de n enteros.

• En este algoritmo se realizan las siguientes operaciones:

• a) Comparación entre mayor1; mayor2 y los elementos del arreglo.

• b) Asignaciones a mayor1 y mayor2• c) Asignación al índice i • d) Asignación a la función• e) Producto de los mayores• f) Incremento al índice • g) Comparación entre el índice i y la longitud del

arreglo n

• Las operaciones (c), (f) y (g) no se consideran por realizarse entre índices,

• las operaciones (d) y (e) se ejecutan una sola vez y no son proporcionales al número total de operaciones. Entonces, se tiene que las operaciones que se pueden considerar para hacer el análisis son: las comparaciones entre mayor1; mayor2 y los elementos del arreglo y las asignaciones a los elementos mayores.

• Resumiendo, el análisis de un algoritmo se puede hacer considerando sólo

• aquella operación que cumpla los siguientes criterios:

• a) Debe estar relacionada con el tipo de problema que se resuelve.

• b) Debe ejecutarse un número de veces cuyo modelo de crecimiento sea similar al del número total de operaciones que efectúa el algoritmo.

• Si ninguna de las operaciones encontradas cumple con ambos criterios, es posible declinar el primero. Si aún así no es posible encontrar una operación representativa, se debe hacer un análisis global, contando todas las operaciones.

• Con los conceptos enunciados hasta aquí es posible calcular la función

• complejidad temporal ft(n) para un algoritmo simple.

• Considérese el siguiente Algoritmo, para hacer el análisis de su comportamiento

• tomemos como operación básica las comparaciones con elementos del arreglo y como caso muestra: A = [2; 7; 4; 1; 3] y n = 5:

• Si Valor = 2, se hace una comparación, ft(5) = 1• Si Valor = 4, se hacen tres comparaciones, ft(5)

= 3• Si Valor = 8, se hacen cinco comparaciones, y

ft(5) = 5

Órdenes de Complejidad

• Se dice que O(f(n)) define un "orden de complejidad". Se elegirá como representante de este orden a la función f(n) más sencilla del mismo.

Así se tiene:

• O(1) orden constante• O(log n) orden logarítmico• O(n) orden lineal• O(n2 ) orden cuadrático• O(n3) orden cubica• O(na) orden polinomial (a > 2)• O(an) orden exponencial (a > 2)• O(n!) orden factorial

• La mejor técnica para diferenciar la eficiencia de los algoritmos es el estudio de los órdenes de complejidad.

• El orden de complejidad se expresa generalmente en términos de la cantidad de datos procesados por el programa, denominada n, que puede ser el tamaño dado o estimado.

Notación Asintótica• El interés principal del análisis de algoritmos

radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece.

• Esto es la eficiencia asintótica del algoritmo.

• Indican como crece t, para valores suficientemente grandes (asintóticamente) sin considerar constantes

Reglas

• Sentencias if

• Suele ser constante O(1)

• Bucles

• for (i=0; i < n; i++) O(n)

• s; O(1)

• for (i=o; i < n i++) O(n)for (j=0; j < n; j++) O(n)

s; O(1)

• h = 1– while (h < n)– {

• s;

• h = 2 * h;

• }

• El logaritmo en base a de un número n, es otro número b, tal que cumple esta ecuación: ab = n.

• for (i=o; i < n i++) O(n)

– for (j=0; j < n; j++)O(n)

s;O(1)

• h = n;

• While (h >1)

• {

• for (i =o; i< n; i++) caso 1 O(n)

• {

• s; } caso 2 O(1)

• h = h/2; caso 3 O(log n) }(while)

Resultado:

• El algoritmo tiene orden de complejidad:

»O (n log n)

• Calcule el orden de complejidad de los siguientes algoritmos:

• i)for( i =0; i<n; i++){• for( j=0; j<n; j++){• suma = 0;• for( k = 0; k<n; k++)

suma += a[i][k] * b[k][j]; }• }

• i= 1;

• while(i <= n)

• {

• x *= 6;

• i++;

• }

• if (x < y)• {• resta = y – x;• }• else• {• resta = x – y;• }

• Fuente Bibliográfica:Pérez Cortés, E. & Kinney Romero, René(2005).Análisis de Algoritmos. Disponible en: http://docencia.izt.uam.mx/pece/pagina_academica/AA/Docum/AAPrimera.PDF

• Análisis de Algorítmos. M.C.C. Ericka Rechy Ramírez• Ejercicios de Complejidad.