SEMANA_07_B1 - meruiz22/Analisis-de-Algoritmos GitHub Wiki

Análisis del caso medio

El análisis del caso medio calcula el tiempo de ejecución esperado de un algoritmo, suponiendo que todas las entradas posibles tienen la misma probabilidad de ocurrir. Es útil cuando el mejor y el peor caso no reflejan adecuadamente el comportamiento del algoritmo en la práctica.

A diferencia del mejor o peor caso, el análisis del caso medio se basa en una distribución de probabilidad sobre las entradas.

Ejemplo: Búsqueda lineal

Supongamos que se busca un elemento en una lista de n elementos, y cada uno tiene igual probabilidad de ser el buscado.

Mejor caso: el elemento está en la primera posición → O(1)
Peor caso: el elemento está en la última posición o no está → O(n)
Caso medio: en promedio, el elemento se encuentra a mitad de camino → O(n/2) → se simplifica a Θ(n)

Importancia

El caso medio es particularmente útil cuando:

Se espera que las entradas sean aleatorias.
Se desea optimizar el comportamiento típico de un sistema.

Análisis amortizado

El análisis amortizado mide el costo promedio por operación de una secuencia de operaciones, incluso si algunas son costosas ocasionalmente. A diferencia del caso medio, no depende de la probabilidad, sino del comportamiento a lo largo del tiempo.

Se usa cuando una operación cara ocurre rara vez y su costo puede distribuirse entre muchas operaciones baratas.

Ejemplo clásico: Vector dinámico (ArrayList)

Supongamos que insertamos elementos en un vector que duplica su tamaño cuando se llena.

La mayoría de inserciones cuestan O(1)
Algunas inserciones requieren copiar todo el arreglo anterior → O(n)
Pero duplicar el tamaño ocurre pocas veces

✅ Amortizado: cada inserción cuesta en promedio O(1) incluso considerando los duplicados.

Métodos comunes de análisis amortizado

Contabilidad (Accounting Method): se asigna un costo "extra" a operaciones baratas para cubrir las caras.
Agregado (Aggregate Method): se analiza el total de operaciones y se divide entre la cantidad total.
Crédito potencial (Potential Method): se mide el cambio en una función de potencial que refleja el trabajo pendiente.

Recurrencias

Una recurrencia es una ecuación que define el tiempo de ejecución de un algoritmo en función del tamaño del problema y el tiempo que tarda en resolver subproblemas.

Son muy útiles para analizar algoritmos recursivos, como divide y vencerás (divide and conquer).

Ejemplo: Merge Sort

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

Significa: dividir el problema en 2 partes de tamaño n/2 y combinarlas en tiempo lineal.

Métodos para resolver recurrencias

Árbol de recurrencia

Se representa visualmente el desglose del problema como un árbol.
Se suman los costos por nivel del árbol para obtener el costo total.

Sustitución (por conjetura)

Se asume una solución (por ejemplo T(n) = O(n log n)).
Se verifica por inducción matemática que la solución satisface la recurrencia.

Teorema maestro (Master Theorem)

Se aplica a recurrencias de la forma:

T(n) = aT(n/b) + f(n) Comparando f(n) con n^log_b(a):

Si f(n) = O(n^c) con c < log_b(a)
⇒ T(n) = Θ(n^log_b(a))
Si f(n) = Θ(n^log_b(a))
⇒ T(n) = Θ(n^log_b(a) * log n)
Si f(n) = Ω(n^c) con c > log_b(a) y se cumple la condición de regularidad
⇒ T(n) = Θ(f(n))

Condición de regularidad: a * f(n/b) ≤ k * f(n) para alguna constante k < 1 y suficientemente grande n.

Ejemplo aplicado

Resolver la recurrencia:

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

Identificamos los parámetros:

a = 2
b = 2
f(n) = n
log_b(a) = log₂(2) = 1

Como f(n) = Θ(n^1) y n^1 = n^log₂(2), estamos en el caso 2 del teorema maestro:

✅ Solución:
T(n) = Θ(n log n)