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

1public class Factorial {
2    public static int factorial(int n) {
3        if (n == 0) return 1;
4        return n * factorial(n - 1);
5    }
6}

✅ Ecuación de Recurrencia: [ T(n) = T(n-1) + O(1) ] 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: [ T(n) = T(n-1) + T(n-2) + O(1) ]

📌 Expandiendo la recurrencia: [ T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) + ... ]

📌 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: [ T(n) = 2T(n/2) + O(n) ]

🔹 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: [ T(n) = aT(n/b) + O(n^d) ] 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

📌 Conclusión:

• Los algoritmos con O(2ⁿ) deben evitarse o mejorar con memorización.
• Divide y vencerás (Merge Sort, QuickSort) son muy eficientes.
• El Método Maestro ayuda a resolver ecuaciones de recurrencia fácilmente.