Introducción a los Algoritmos – Parte II – Eficiencia de Algoritmos

Link a la primer parte 😀

Un objetivo natural en el desarrollo de un programa computacional es mantener tan bajo como sea posible el consumo de los diversos recursos, aprovechándolos de la mejor manera que se encuentre. Se desea un buen uso, eficiente, de los recursos disponibles, sin desperdiciarlos.

Para que un programa sea práctico, en términos de requerimientos de almacenamiento y tiempo de ejecución, debe organizar sus datos en una forma que apoye el procesamiento eficiente. Siempre que se trata de resolver un problema, puede interesar considerar distintos algoritmos, con el fin de utilizar el más eficiente. Pero, ¿cómo determinar cuál es “el mejor”?. La estrategia empírica consiste en programar los algoritmos y ejecutarlos en un computador sobre algunos ejemplares de prueba. La estrategia teórica consiste en determinar matemáticamente la cantidad de recursos (tiempo, espacio, etc.) 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 el computador. Pero a nivel algorítmico consideraremos 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, el análisis de resolución del problema se lo realiza prioritariamente.
Puede darse el caso de que exista un algoritmo eficaz pero no eficiente, en lo posible debemos de manejar estos dos conceptos conjuntamente.

La eficiencia de un programa tiene dos ingredientes 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.

Ambas dependen del tipo de computador y compilador, por lo que no se estudiará aquí la eficiencia de los programas, sino la eficiencia de los algoritmos. Asimismo, este análisis dependerá de si trabajamos con máquinas de un solo procesador o de varios de ellos. Centraremos nuestra atención en los algoritmos para máquinas de un solo procesador que ejecutan una instrucción y luego otra.

 

Medidas de Eficiencia

Inventar algoritmos es relativamente fácil. En la práctica, sin embargo, no se pretende sólo diseñar algoritmos, si no más bien que buenos algoritmos. Así, el objetivo es inventar algoritmos y probar que ellos mismos son buenos.

La calidad de un algoritmo puede ser avalada utilizando varios criterios. Uno de los criterios más importantes es el tiempo utilizado en la ejecución del algoritmos. Existen varios aspectos a considerar en cada criterio de tiempo. Uno de ellos está relacionado con el tiempo de ejecución requerido por los diferentes algoritmos, para encontrar la solución final de un problema o cálculo particular.
Normalmente, un problema se puede resolver por métodos distintos, con diferentes grados de eficiencia. Por ejemplo: búsqueda de un número en una guía telefónica.

Cuando se usa un computador es importante limitar el consumo de recursos.

Recurso de 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 de Memoria

  • Las máquinas tienen una memoria limitada .

 

Análisis A Priori y Prueba A Posteriori

El análisis de la eficiencia de los algoritmos (memoria y tiempo de ejecución) consta de dos fases: Análisis A Priori y Prueba A Posteriori.

El Análisis A Priori (o teórico) entrega una función que limita el tiempo de cálculo de un algoritmo. Consiste en obtener una expresión que indique el comportamiento del algoritmo en función de los parámetros que influyan.

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.

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 un computador sobre algunos ejemplares de prueba, haciendo medidas para:

  • una máquina concreta,
  • un lenguaje concreto,
  • un compilador concreto y
  • datos concretos

La estrategia teórica tiene como ventajas que no depende del computador ni del lenguaje de programación, ni siquiera de la habilidad del programador. Permite evitar el esfuerzo inútil de programar algoritmos ineficientes y de despediciar tiempo de máquina para ejecutarlos. También permite conocer la eficiencia de un algoritmo cualquiera que sea el tamaño del ejemplar al
que se aplique.

 

Concepto de Instancia

Un problema computacional consiste en una caracterización de un conjunto de datos de entrada, junto con la especificación de la salida deseada en base a cada entrada.

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.

Ejemplo: el problema computacional de multiplicar dos números enteros tiene por ejemplo, las siguientes instancias: multiplicar 345 por 4653, multiplicar 2637 por 10000, multiplicar -32341 por 12, etc.

Un problema computacional abarca a otro problema computacional si las instancias del segundo pueden ser resueltas como instancias del primero en forma directa.

 

Tamaño de los Datos

Variable o expresión en función de la cual intentaremos medir la complejidad del algoritmo.

Es claro que para cada algoritmo la cantidad de recurso (tiempo, memoria) utilizados depende fuertemente de los datos de entrada. En general, la cantidad de recursos crece a medida que crece el tamaño de la entrada.

El análisis de esta cantidad de recursos no es viable de ser realizado instancia por instancia. 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 la cantidad de dígitos para un número, la cantidad de elementos para un arreglo, la cantidad de caracteres de una cadena, en problemas de ordenación es el número de elementos a ordenar, en matrices puede ser el número de filas, columnas o elementos totales, en algoritmos recursivos es el número de recursiones o llamadas propias que hace la función.

En ocasiones es útil definir el tamaño de la entrada en base a dos o más magnitudes. Por ejemplo, para un grafo es frecuente utilizar la cantidad de nodos y de arcos.

En cualquier caso, se debe elegir la misma variable para comparar algoritmos distintos aplicados a los mismos datos.

 

Cálculo de Costos de Algoritmos

Queremos saber la eficiencia de los algoritmos, no del computador. Por ello, en lugar de medir el tiempo de ejecución en microsegundos o algo por el estilo, nos preocuparemos del número de veces que se ejecuta una operación primitiva (de tiempo fijo).

Para estimar la eficiencia de este algoritmo, podemos preguntarnos, “si el argumento es una frase de N números, ¿cuántas multiplicaciones realizaremos?” La respuesta es que hacemos una multiplicación por cada número en el argumento, por lo que hacemos N multiplicaciones. La cantidad de tiempo que se necesitaría para el doble de números sería el doble.

 

Cálculo de Eficiencia en Análisis Iterativo

Cuando se analiza la eficiencia, en tiempo de ejecución, de un algoritmo son posibles distintas aproximaciones: desde el cálculo detallado (que puede complicarse en muchos algoritmos si se realiza un análisis para distintos contenidos de los datos de entrada, casos más favorables, caso peor, hipótesis de distribución probabilística para los contenidos de los datos de entrada, etc.) hasta el análisis asintótico simplificado aplicando reglas prácticas.

En estos apuntes se seguirá el criterio de análisis asintótico simplificado, si bien nunca se ha de dejar de aplicar el sentido común. Como en todos los modelos simplificados se ha mantener la alerta para no establecer hipótesis simplificadoras que no se correspondan con la realidad.

En lo que sigue se realizará una exposición basada en el criterio de exponer en un apartado inicial una serie de reglas y planteamientos básicos aplicables al análisis de eficiencia en algoritmos iterativos, en un segundo apartado se presenta una lista de ejemplos que permitan comprender algunas de las aproximaciones y técnicas expuestas.

 

Cálculo de Eficiencia en Análisis Recursivo

Retomando aquí el socorrido ejemplo del factorial, tratemos de analizar el coste de dicho algoritmo, en su versión iterativa , se tiene:

PROCEDURE Factorial(n : CARDINAL) : CARDINAL
    BEGIN
        VAR Resultado,i : CARDINAL ;
        Resultado :=1 ;
        FOR i :=1 TO n DO
         Resultado :=Resultado*i ;
        END ;
        RETURN Resultado
    END Factorial ;

Aplicando las técnicas de análisis de coste en algoritmos iterativos de forma rápida y mentalmente (es como se han de llegar a analizar algoritmos tan simples como éste), se tiene: hay una inicialización antes de bucle, de coste constante. El bucle se repite un número de veces n y en su interior se realiza una operación de coste constante. Por tanto el algoritmo es de coste lineal o
expresado con algo más de detalle y rigor, si la función de coste del algoritmo se expresa por T(n), se tiene que T(n) ? T.

Una versión recursiva del mismo algoritmo, es:

PROCEDURE Factorial(n: CARDINAL): CARDINAL;
    BEGIN
        IF n=0 THEN
            RETURN 1
        ELSE
            RETURN ( n* Factorial(n-1) )
        END
    END Factorial;

Al aplicar el análisis de coste aprendido para análisis de algoritmos iterativos se tiene: hay una instrucción de alternativa, en una de las alternativas simplemente se devuelve un valor (operación de coste constante). En la otra alternativa se realiza una operación de coste constante (multiplicación) con dos operandos. El primer operando se obtiene por una operación de coste constante (acceso a la variable n), el coste de la operación que permite obtener el segundo operando es el coste que estamos calculando!, es decir es
el coste de la propia función factorial (solo que para parámetro n-1).

Por tanto, para conocer el orden de la función de coste de este algoritmo ¿debemos conocer previamente el orden de la función de coste de este algoritmo?, entramos en una recurrencia.

Y efectivamente, el asunto está en saber resolver recurrencias. Si T(n) es la función de coste de este algoritmo se puede decir que T(n) es igual a una operación de coste constante c cuando n vale 0 y a una operación de coste T(n-1) más una operación de coste constante (el acceso a n y la multiplicación) cuando n es mayor que 0, es decir:

Se trata entonces de encontrar soluciones a recurrencias como ésta. Entendiendo por solución una función simple f(n) tal que se pueda asegurar que T(n) es del orden de f(n).

En este ejemplo puede comprobarse que T(n) es de orden lineal, es decir del orden de la función f(n)=n, ya que cualquier función lineal T(n)= an+siendo a y b constantes, es solución de la recurrencia:

  • T(0)= b , es decir una constante
  • T(n)= a.n+b= ana+ b+a= a(n-1)+b+a= T(n-1)+a, es decir el coste de T(n) es igual al de T(n-1) más una constante.

 

Principio de Invarianza

Dado un algoritmo y dos implementaciones I1 y I2 (máquinas distintas o códigos distintos) que tardan T1(n) y T2(n) respectivamente, el principio de invarianza afirma que existe una constante real c>0 y un número natural ntales que para todo n>=n0 se verifica que T1(n)<=c·T2(n).

Es decir, el tiempo de ejecución de dos implementaciones distintas de un algoritmo dado no va a diferir más que en una constante multiplicativa.

Asumimos que un algoritmo tarda un tiempo del orden de T(n) si existen una constante real c>0 y una implementación I del algoritmo que tarda menos que c·T (n), para todo n tamaño de entrada.

El comportamiento de un algoritmo puede variar notablemente para diferentes secuencias de entrada. Suelen estudiarse tres casos para un mismo algoritmo: caso mejor, caso peor, caso medio.

 

Análisis Peor Caso, Mejor Caso y Caso Promedio

Puede analizarse un algoritmo particular o una clase de ellos. Una clase de algoritmo para un problema son aquellos algoritmos que se pueden clasificar por el tipo de operación fundamental que realizan.

  • Ejemplo:
    • Problema: Ordenamiento
    • Clase: Ordenamiento por comparación

Para algunos algoritmos, diferentes entradas (inputs) para un tamaño dado pueden requerir diferentes cantidades de tiempo.
Por ejemplo, consideremos el problema de encontrar la posición particular de un valor K, dentro de un arreglo de n elementos.

Suponiendo que sólo ocurre una vez. Comentar sobre el mejor, peor y caso promedio.

¿Cuál es la ventaja de analizar cada caso? Si examinamos el peor de los casos, sabemos que al menos el algoritmo se desempeñará de esa forma.

En cambio, cuando un algoritmo se ejecuta muchas veces en muchos tipos de entrada, estamos interesados en el comportamiento promedio o típico.

Desafortunadamente, esto supone que sabemos cómo están distribuidos los datos.

Si conocemos la distribución de los datos, podemos sacar provecho de esto, para un mejor análisis y diseño del algoritmo. Por otra parte, sino conocemos la distribución, entonces lo mejor es considerar el peor de los casos.

Tipos de análisis:

  • Peor caso: indica el mayor tiempo obtenido, teniendo en consideración todas las entradas pos ibles.
  • 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.

Como no se puede analizar el comportamiento sobre todas las entradas posibles, va a existir para cada prob lema particular un análisis en él:

  • peor caso
  • mejor caso
  • caso promedio (o medio)

El caso promedio es la medida más realista de la performance, pero es más difícil de calcular pues establece que todas las entradas son igualmente probables, lo cual puede ser cierto o no. Trabajaremos específicamente con el peor caso.

 

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 ……….<=A
  • Descendente A1 >=A2 >=……..>=A

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.


 

1 pensamiento en “Introducción a los Algoritmos – Parte II – Eficiencia de Algoritmos”

  1. Pingback: Introducción a los Algoritmos – Parte III – Análisis de Algoritmos – La Compu Del Vecino

Dejá un comentario