Analisis Computacional De Algoritmos

INTRODUCCION

Un buen algoritmo no debe depender del sistema en el que se ejecuta. Generalmente cuando hablamos del sistema informático en relación al análisis del coste computacional englobamos: sistema operativo, hardware, lenguaje de programación, RAM, velocidad de CPU, etc.

Ejemplo: examinamos 2 algoritmos de ordenación, burbuja y QuickSort, cual es el tiempo utilizado para ordenar un vector de 1000000 elementos:

• PC AMD Athlon XP2800+ 2.08 GHz 512 RAM usando el algoritmo de ordenación QuickSort: Tiempo de ejecución 8 segundos.

• IBM Star usando el algoritmo de ordenación de la burbuja: Tiempo de ejecución 6 minutos.

El IBM Star es 160 veces más rápido que el PC, podemos comprobar que el algoritmo de ordenación QuickSort para grandes conjuntos de datos es más eficiente que el algoritmo de ordenación por burbuja, independientemente del sistema con que se ejecute.

MARCO TEORICO

1. Costo Computacional de Algoritmos

El responsable principal de la eficiencia de un algoritmo es el programador

1.1. ¿Cómo podemos medir el coste computacional de un algoritmo?

Vamos a establecer un sistema muy simple, lógico y sencillo Si damos un tiempo de ejecución a cada operación elemental y contamos el número de operaciones elementales que habrá en un algoritmo en concreto, podremos conocer el coste temporal de ejecución.

Supongamos el siguiente algoritmo:

1: Para (i desde 1 hasta n) hacer

2: pmin := i;

3: Para (j desde i+1 hasta n) hacer

4: Si (a[j] < a[pmin]) entonces pmin := j

Finsi

FinPara

5: intercanviar(a[i],a[pmin]);

FinPara

Para medir su coste computacional (en tiempo) en función del tamaño de los datos "n" deberemos establecer una serie de constantes(Cada una con su cantidad de ciclos de CPU).

ta: tiempo de una instrucción de asignación de enteros.

tc: tiempo de una instrucción de comparación de enteros.

ti: tiempo de una instrucción de incremento de un entero.

tv: tiempo de una instrucción de acceso a un elemento de un vector.

Analicemos ahora el coste de cada instrucción de nuestro algoritmo:

instrucción 1: ta + (n-1)•ti + n•tc

instrucción 2: (n-1)•ta

instrucción 3 (para un i): ta + (n-1)•ti + (n-i+1)•tc

instrucción 4 (para un i): Mejor caso = (n-i) • (2•tv+tc) || Peor caso = (n-i) • (2•tv+tc) + ((n-i)•ta

instrucción 5: (n-1) • (2•tv + 3•ta)

Como la instrucción "4" de nuestro algoritmo es una alternativa tendremos que establecer un criterio de selección. Es interesante averiguar cuál es la cota superior de consumo de tiempo del algoritmo, sería mejor examinar el coste computacional del algoritmo en el peor de los casos (siempre se cumple la condición de la instrucción "4"). La expresión final que indicara el coste computacional del algoritmo en el peor de los casos será:

Consideraciones sobre el resultado alcanzado. El tiempo de ejecución del algoritmo analizado depende de tres factores:

1. El tamaño que tenga el conjunto de los datos de entrada de nuestro algoritmo, representado en éste por el parámetro "n".

2. El contenido de los datos de entrada, que hace que el tiempo de ejecución oscile entre el mejor caso y el peor.

3. El código generado por un compilador y computador en concreto.

Podríamos establecer las siguientes expresiones como cotas inferior y superior respectivamente del análisis de coste computacional:

(El orden máximo de los polinomios resultantes en ambos casos es cuadrático)

Ahora podemos cuestionarnos si es necesario realizar un análisis de los tiempos de computación tan detallado (como el recién realizado) o bastaría hacerlo de forma aproximada. Si se desea analizar un algoritmo complejo, el tiempo invertido en el análisis puede ser inaceptable en la práctica.

El análisis del coste computacional de los algoritmos lo estimaremos siempre en el peor de los casos, ya que el caso promedio es en muchas ocasiones difícil de establecer.

Tomaremos en consideración el tamaño de los datos de entrada centrado el análisis de eficiencia de algoritmos en base al tamaño del conjunto de datos para comparar eficiencia de varios algoritmos basado en rapidez en que el algoritmo alcanza la solución del problema.

1.2. Criterio Asintótico

Al tener gran conjunto de datos a tratar, la constante multiplicativa c desprecia frente a la complejidad computacional del algoritmo.

El gran consumo de memoria para un determinado algoritmo va en desmedro a la eficacia computacional del mismo.

Ejemplo:

-(CASO A) Queremos q un algoritmo calcule los "n" primeros números primos, el algoritmo básico que divide cada número por los anteriores, no consumiremos memoria pero debemos efectuar todas las divisiones posibles ya q no hay información anterior sobre si un número menor es o no primo

-(CASO B) Diseñamos un algoritmo va guardando números primos calculados antes para saber si un número es o no primo dividirlo por los primos anteriores, aquí la eficiencia computacional es mejor pero habrá mayor consumo de memoria

1.3. Conclusión

En este aspecto es primordial entender y aceptar que el programador siempre es el responsable final de decidir donde sitúa el punto de equilibrio entre eficiencia en tiempo de ejecución y consumo de memoria, decisión que puede venir condicionada o no por los requerimientos iniciales

...