Semana 7 - leosaq/AnalisisDeAlgoritmos GitHub Wiki
Análisis del Caso Medio
El análisis del caso medio estima el comportamiento promedio de un algoritmo al considerar todas las posibles entradas de cierto tamaño y calcular una media ponderada del tiempo que tomaría ejecutarse.
¿Por qué es importante?
Mientras el peor caso indica el límite superior y el mejor caso el límite inferior, el caso medio nos da una visión más realista de cómo se desempeñará el algoritmo en la práctica.
Ejemplo:
En el algoritmo de búsqueda binaria, aunque el peor caso toma log₂(n) comparaciones, en promedio se suele encontrar el elemento antes, por lo que el análisis del caso medio ayuda a comprender ese rendimiento intermedio.
Análisis Amortizado
El análisis amortizado se utiliza para estudiar algoritmos donde algunas operaciones pueden ser costosas, pero su costo se distribuye equitativamente a lo largo de muchas ejecuciones, resultando en un costo promedio más bajo por operación.
Tipos de análisis amortizado:
- Método agregado: Se calcula el costo total de una secuencia de operaciones y se divide entre ellas.
- Método contable: Se asigna un "crédito" a cada operación para cubrir futuros gastos costosos.
- Método del potencial: Se usa una función que mide el estado del sistema y ayuda a distribuir el costo.
Ejemplo:
El redimensionamiento de un arreglo dinámico (ArrayList) puede parecer costoso, pero si se analiza en conjunto, la mayoría de inserciones cuestan O(1), y solo algunas pocas requieren copiar todo el arreglo.
Recurrencias
Las recurrencias son ecuaciones que definen el tiempo de ejecución de un algoritmo de forma recursiva. Se usan comúnmente para analizar algoritmos recursivos, como los de tipo "divide y vencerás".
¿Cómo se resuelven?
Las recurrencias pueden resolverse usando métodos como:
- Expansión repetida (desenrollar la recurrencia)
- Árbol de recurrencia
- Teorema Maestro (Master Theorem)
Ejemplo:
El algoritmo de Merge Sort tiene la recurrencia:
T(n) = 2T(n/2) + O(n)
Esto indica que divide el problema en 2 partes de tamaño n/2, y luego combina los resultados en tiempo lineal. Resolviendo esta recurrencia, obtenemos que su complejidad es O(n log n).
Taller 1 en Clase
Solución
Taller 2
Solución
Se analizó el algoritmo de Fibonacci identificando su recurrencia, obteniendo su ecuación general mediante el método de ecuaciones características, y demostrando su validez por inducción matemática. Este análisis permite comprender el crecimiento del algoritmo y su comportamiento computacional.