3. Análisis de algoritmos

El análisis de algoritmos permite determinar la eficiencia y el comportamiento de un algoritmo, usualmente en función del tamaño de entrada n. Es fundamental para comparar diferentes soluciones y optimizar códigos en escenarios prácticos.

---

3.2. Análisis del caso medio

Introducción

El análisis del caso medio evalúa el rendimiento esperado de un algoritmo en condiciones típicas, suponiendo una distribución uniforme o probabilidad conocida para las entradas.

Enfoque

• Se calcula el tiempo o pasos promedio que tarda el algoritmo en procesar entradas de tamaño n.
• Es útil cuando el peor caso es poco frecuente pero puede ser relevante para entender rendimiento general en uso cotidiano.

Ejemplo

Para un algoritmo de búsqueda en una lista desordenada, el tiempo medio puede estimarse suponiendo que cada elemento tiene igual probabilidad de ser la clave buscada. En promedio, esto sería O(n), ya que, en el peor caso, hay que revisar la mitad de la lista.

---

3.3. Análisis amortizado

Introducción

El análisis amortizado evalúa el coste promedio de operaciones en una secuencia de acciones, considerando que algunas operaciones pueden ser costosas pero infreqentes, y otras económicas.

Enfoque

• Se calcula el coste total de m operaciones y se divide entre ellas para obtener un coste medio por operación.
• Es útil en estructuras de datos dinámicas como pilas, colas, arreglos dinámicos, árboles, donde algunas operaciones tienen costos ocasionalmente altos.

Ejemplo

En un arreglo dinámico que duplica su tamaño cuando se llena:

• La operación de inserción puede costar O(n) en un caso particular (al redimensionar).
• Sin embargo, a largo plazo, la operación promedio por inserción sigue siendo O(1), ya que los costos elevados se distribuyen en muchas operaciones menos costosas.

---

3.4. Recurrencias

Introducción

Las recurrencias son ecuaciones que describen la estructura recursiva de un algoritmo, particularmente para determinar su tiempo de ejecución en función del tamaño de la entrada n.

Método de resolución

• Expansión o desdoblamiento: descomponer la recurrencia varias veces y buscar un patrón.
• Método de sustitución: hacer una conjetura sobre la solución y demostrarla por inducción.
• Árbol de recurrencias: visualizar costos en niveles.
• Teorema de Master: resolver recurrencias del tipo T(n) = aT(n/b) + f(n) rápidamente.

Ejemplo

Consideremos:

T(n) = 2T(n/2) + n