Recurrencias y el Método Maestro

En esta sección aprenderemos a analizar la complejidad de algoritmos recursivos y a resolver ecuaciones de recurrencia usando el Método Maestro.

✅ Objetivo:

• Comprender cómo crecen los algoritmos recursivos.
• Aprender a resolver ecuaciones de recurrencia para calcular su complejidad.
• Aplicar el Método Maestro para analizar Divide y Vencerás.

1. ¿Qué es una Ecuación de Recurrencia? #

Los algoritmos recursivos llaman a sí mismos con valores más pequeños de n, lo que nos lleva a una ecuación de recurrencia.

📌 Ejemplo: Recursión básica

✅ Ecuación de Recurrencia:

Cada llamada reduce n en 1, por lo que la complejidad es O(n).

2. Resolviendo Ecuaciones de Recurrencia #

Para analizar la complejidad de un algoritmo recursivo, expansimos la recurrencia hasta encontrar un patrón.

Ejemplo: Fibonacci Recursivo #

1// Java - O(2ⁿ) - Fibonacci Recursivo
2public class Fibonacci {
3    public static int fib(int n) {
4        if (n <= 1) return n;
5        return fib(n - 1) + fib(n - 2);
6    }
7}

✅ Ecuación de Recurrencia:

📌 Expandiendo la recurrencia:

📌 Conclusión:
El tiempo de ejecución duplica en cada paso, por lo que la complejidad es O(2ⁿ) (Explosión combinatoria 🚨).

🚀 Solución:
Memorización para reducirlo a O(n).

3. Método Maestro para Divide y Vencerás #

Los algoritmos como Merge Sort y QuickSort siguen un patrón de Divide y Vencerás.

📌 Ejemplo: Merge Sort

1// Java - O(n log n) - Merge Sort
2public class MergeSort {
3    public static int[] sort(int[] arr) {
4        if (arr.length <= 1) return arr;
5        int mid = arr.length / 2;
6        int[] left = sort(Arrays.copyOfRange(arr, 0, mid));
7        int[] right = sort(Arrays.copyOfRange(arr, mid, arr.length));
8        return merge(left, right);
9    }
10}

✅ Ecuación de Recurrencia:

🔹 Explicación:

• 2T(n/2): Se divide el problema en dos mitades.
• O(n): Se combina la solución en tiempo lineal.

📌 Método Maestro (Regla General): Si una recurrencia tiene la forma:

Usamos la siguiente regla:

4. Ejemplos con el Método Maestro #

Ejemplo 1: Merge Sort (O(n log n)) #

• Ecuación: $$T(n) = 2T(n/2) + O(n)$$
• Valores:
  • a = 2, b = 2, d = 1
  • log_2(2) = 1
• Conclusión:
  d = log_b(a), por lo que la complejidad es O(n log n).

✅ Conclusión:
El Merge Sort y otros algoritmos similares tienen O(n log n).

Ejemplo 2: Búsqueda Binaria (O(log n)) #

• Ecuación: $$T(n) = T(n/2) + O(1)$$
• Valores:
  • a = 1, b = 2, d = 0
  • log_2(1) = 0
• Conclusión:
  d < log_b(a), por lo que la complejidad es O(log n).

✅ Conclusión:
La búsqueda binaria es muy eficiente (O(log n)), porque reduce el problema a la mitad en cada paso.

5. Comparación de Algoritmos Recursivos #