## 1.1 EL ROL DE LOS ALGORITMOS EN LA COMPUTACIÓN (continuación)

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.

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, si no 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 posibles.
- 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 problema 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 eficiencia, 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 en un vector. Ordenar significa permutar estos elementos de tal forma que los mismos queden de acuerdo con un orden preestablecido.
Ascendente A1<=A2<=A3..........<=An
Descendente A1>=A2>=A3........>=An

- 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.

Tiempos de ejecución

Una medida que suele ser útil conocer es el tiempo de ejecución de un algoritmo en función de N, lo que denominaremos T(N) o f(n). Esta función se puede medir físicamente (ejecutando el programa), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción.

Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que más que un valor T(N) debamos hablar de un rango de valores:
Tmin(N) <= T(N) <= Tmax(N) los extremos son habitualmente conocidos como caso peor y caso mejor.

Entre ambos se hallará algún caso promedio o más frecuente. Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes Tique dependen de factores externos al algoritmo como pueden ser la calidad del código generado por el compilador y la velocidad de ejecución de instrucciones del computador que lo ejecuta.

No se puede medir el tiempo en segundos porque no existe una computadora estándar de referencia, en su lugar medimos el número de operaciones básicas o elementales.

Las operaciones básicas son las que realiza la computadora en tiempo acotado por una constante, por ejemplo:

• Operaciones aritméticas básicas.
• Asignaciones de tipos predefinidos.
• Saltos (llamadas a funciones, procedimientos y retorno).
• Comparaciones lógicas.
• Acceso a estructuras indexadas básicas (vectores y matrices).

Es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentencias, por ejemplo, las que más influyen en el tiempo de ejecución.

El tiempo de ejecución puede ser definido como una función de la entrada. Denotaremos T(n) como el tiempo de ejecución de un algoritmo para una entrada de tamaño n.

Ejemplo Búsqueda lineal

    func BusquedaLineal(Valor,A,n)
    {

       i=1;

       while(i<=n&&A[i]!=Valor)

       {

          i=i+1;

       }

       return i;

    }

Operación básica: En el Algoritmo de búsqueda lineal es la comparación entre los elementos del arreglo y el valor.

"Comparación A[i]!=Valor"

Caso 0: Valor=11, A={49,12,56,90,2,5,11,32,22,7}, n=10

Si el Valor=11: se entra al ciclo 6 veces -> n=6

Si el ciclo se ejecutará n veces:
n sumas (una por cada iteración).
n + 2 asignaciones (las del ciclo y las realizadas fuera del ciclo).
n + 1 operaciones lógicas (la condición se debe probar n + 1 veces, la última es para saber que el ciclo no debe volver a ejecutarse).
n + 1 comparaciones con el índice.
n + 1 comparaciones con elementos de A:
n + 1 accesos a elementos de A:
6n + 6 operaciones en total.

n | instrucciones
0 | 6
1 | 12
10 | 66
100 | 606
500 | 3006
1000 | 6006

- Mejor caso: ocurre cuando el valor es el primer elemento del arreglo.
  f(n)= 1 (1 Comparación)
- Peor caso: sucede cuando el valor no se encuentra en el arreglo.
  f(n)=n + 1 (n+1 Comparaciones)
- Caso medio:
  f(n)=1P(1) + 2P(2) + 3P(3) + 4P(4) +... + nP(n) + (n+1)P(n + 1). Donde P(i) es la probabilidad de que el valor se encuentre en la localidad i; (1 ≤ i ≤ n) y P(n + 1) es la probabilidad de que no esté en el arreglo y el número que lo acompaña es la cantidad de operaciones básicas para cada uno de ellos.

###