Algoritmo De La Cota Superior

Análisis de Algoritmos

• El análisis de algoritmos estima el consumo de recursos de un algoritmo.

• Esto nos permite comparar los costos relativos de dos o más algoritmos para resolver el mismo problema.

• El análisis de algoritmos también les da una herramienta a los diseñadores de algoritmos para estimar si una solución propuesta es probable que satisfaga las restricciones de recursos de un problema.

• El concepto de razón de crecimiento, es la razón a la cual el costo de un algoritmo crece conforme el tamaño de la entrada crece.

Introducción

• ¿Cómo comparar dos algoritmos para resolver un mismo problema en términos de eficiencia?

• El análisis de algoritmos mide la eficiencia de un algoritmo, conforme crece el tamaño de la entrada.

• Usualmente se mide el tiempo de ejecución de un algoritmo, y el almacenamiento primario y secundario que consume.

• De consideración principal para estimar el desempeño de un algoritmo, es el número de operaciones básicas requeridas por el algoritmo para procesar una entrada de cierto tamaño.

• Ejemplo: algoritmo de búsqueda secuencial del máximo. T(n) = cn (donde c es el tiempo que lleva examinar una variable).

int largest (int* array, int n)

{ int currlarge=0;

for(int i = 0, i < n; i++)

if(array[i] > currlarge)

currlarge = array[i];

return currlarge;

}

• Ejemplo: el tiempo requerido para copiar la primera posición de un arreglo es siempre c1 (independientemente de n). Asi T(n) = c1.

• Ejemplo :

Sum=0 ;

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

for(j=1; j <= n; j++)

sum++;

¿Cuál es el tiempo de ejecución de este fragmento de código? T(n) = c2 n2 (c2 es el tiempo en incrementar una variable).

• El concepto de razón de crecimiento es extremadamente importante. Nos permite comparar el tiempo de ejecución de dos algoritmos sin realmente escribir dos programas y ejecutarlas en la misma máquina.

• Una razón de crecimiento de cn se le llama a menudo razón de crecimiento lineal.

• Si la razón de crecimiento tiene el factor n2, se dice que tiene una razón de crecimiento cuadrático.

• Si el tiempo es del orden 2n se dice que tiene una razón de crecimiento exponencial.

• notemos que 2n> 2n2 >log n

• también para toda a, b > 1, na > (log n)b y na > log nb

• para toda a, b >1, an > nb

Mejor, peor y caso promedio

• 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ñara 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 considerar el peor de los casos.

¿Una computadora más rápida o un algoritmo más rápido?

• Si compramos una computadora diez veces más rápida, ¿en qué tiempo podremos ahora ejecutar una algoritmo?

• La respuesta depende del tamaño de la entrada de datos, así como en la razón de crecimiento del algoritmo.

• Si la razón de crecimiento es lineal (i.e. T(n)=cn) entonces por ejemplo, 100,000 números serán procesados en la nueva máquina en el mismo tiempo que 10,000 números en la antigua computadora.

...