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.

• ¿De que tamaño (valor de n) es el problema que podemos resolver con una computadora X veces más rápida (en un intervalo de tiempo fijo)?

• Por ejemplo, supongamos que una computadora resuelve un problema de tamaño n en una hora. Ahora supongamos que tenemos una computadora 10 veces más rápida, ¿de que tamaño es el problema que podemos resolver?

f(n) n n´ cambio n´/n

10n 1000 10000 n´=10n 10

20n 500 5000 n´=10n 10

5n log n 250 1842 Ö(10)n <n´<10n 7.37

2n2 70 223 n´=Ö(10)n 3.16

2n 13 16 n´=n+3 ----

• En la tabla de arriba, f(n) es la razón de crecimiento de un algoritmo.

• Supongamos que tenemos una computadora que puede ejecutar 10,000 operaciones básicas en una hora.

• La segunda columna muestra el máximo valor de n que puede ejecutarse con 10,000 operaciones básicas en una hora.

• Es decir f(n)=total de op. básicas en un int. de Tiempo

• Por ejemplo, f(n)=10,000 operaciones b. por hr.

• Si suponemos que tenemos una computadora 10 veces más rápida, entonces podremos ejecutar 100,000 operaciones básicas en una hora.

• Por lo cual f(n´)=100,000 op. bas. por hr.

• Comentar sobre la razón n´/n según el incremento de velocidad de la computadora y la razón de crecimiento del algoritmo en cuestión.

Nota: los factores constantes nunca afectan la mejora relativa obtenida por una computadora más rápida.

Análisis Asintótico

• Comparemos la razón de crecimiento entre 10n, 20n, y 2n2, notaremos que 2n2, supera eventualmente a 10n y 20n, difiriendo solamente en un valor mayor de n, donde ocurre el corte.

• Por las razones anteriores, usualmente se ignoran las constantes cuando queremos una estimación del tiempo de ejecución u otros requerimientos de recursos del algoritmo. Esto simplifica el análisis y nos mantiene pensando

...