Costo Computacional De Algoritmos

Costo Computacional de Algoritmos

Un buen algoritmo no debe depender del sistema en el que se ejecuta. Generalmente cuando hablamosdel 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 elalgoritmo 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ápidoque 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 quese ejecute.

El responsable principal de la eficiencia de un algoritmo es el programador
¿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 deejecució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 fsi
fpara
5: intercanviar(a[i],a[pmin]);
fpara
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...