Complejidad de Algoritmos Recursivos

Análisis de recursión

Analizar la complejidad de funciones recursivas requiere:

1. Identificar la relación de recurrencia
2. Resolver la recurrencia o aplicar el teorema maestro

Recurrencias comunes

Recursión lineal

void f(int n) {
    if (n == 0) return;
    // O(1) trabajo
    f(n - 1);  // Una llamada
}

Recurrencia: $T(n) = T(n-1) + O(1)$

Complejidad: $O(n)$

Recursión con trabajo lineal

void f(int n) {
    if (n == 0) return;
    for (int i = 0; i < n; i++) {  // O(n) trabajo
        // ...
    }
    f(n - 1);
}

Recurrencia: $T(n) = T(n-1) + O(n)$

Complejidad: $O(n^2)$

División por 2 (Búsqueda binaria)

int buscar(vector<int>& arr, int x, int l, int r) {
    if (l > r) return -1;
    int mid = (l + r) / 2;  // O(1) trabajo
    if (arr[mid] == x) return mid;
    if (arr[mid] < x) return buscar(arr, x, mid+1, r);
    return buscar(arr, x, l, mid-1);  // Una llamada
}

Recurrencia: $T(n) = T(n/2) + O(1)$

Complejidad: $O(\log n)$

Divide y vencerás (Merge Sort)

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);       // T(n/2)
    mergeSort(mid + 1, r);   // T(n/2)
    merge(l, mid, r);        // O(n) trabajo
}

Recurrencia: $T(n) = 2T(n/2) + O(n)$

Complejidad: $O(n \log n)$

El Teorema Maestro

Para recurrencias de la forma: $T(n) = aT(n/b) + f(n)$

Donde:

• $a$ = número de subproblemas
• $b$ = factor de reducción
• $f(n)$ = trabajo fuera de la recursión

Casos del teorema

Sea $c = \log_b a$:

1. Si $f(n) = O(n^{c-\epsilon})$: $T(n) = \Theta(n^c)$
2. Si $f(n) = \Theta(n^c)$: $T(n) = \Theta(n^c \log n)$
3. Si $f(n) = \Omega(n^{c+\epsilon})$: $T(n) = \Theta(f(n))$

Ejemplos de aplicación

Fibonacci: un análisis detallado

Sin memorización

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Recurrencia: $T(n) = T(n-1) + T(n-2) + O(1)$

Complejidad: $O(\phi^n) \approx O(1.618^n)$ - ¡Exponencial!

Cota superior: $O(2^n)$

Con memorización

int memo[N];
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

Complejidad: $O(n)$ - Cada estado se calcula exactamente una vez.

Complejidad espacial

La recursión usa espacio en la pila de llamadas:

void f(int n) {
    if (n == 0) return;
    f(n - 1);  // Llamada pendiente
}

Espacio: $O(n)$ - profundidad máxima de la pila.

Recursión de cola (optimizable)

// Puede optimizarse a O(1) espacio
int factorialCola(int n, int acc = 1) {
    if (n <= 1) return acc;
    return factorialCola(n - 1, n * acc);
}

Divide y vencerás

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    merge(l, mid, r);
}

Espacio en pila: $O(\log n)$ - profundidad del árbol de recursión.

Análisis de árboles de recursión

Método del árbol

Para $T(n) = 2T(n/2) + n$:

Nivel 0:       n                    -> n
Nivel 1:    n/2   n/2               -> n
Nivel 2:  n/4 n/4 n/4 n/4           -> n
...
Nivel k: ...                        -> n

Profundidad: log₂(n)
Total: n × log₂(n) = O(n log n)

Ejemplo: Potencia rápida

long long pot(long long a, long long n) {
    if (n == 0) return 1;
    long long medio = pot(a, n/2);  // Una llamada
    return (n % 2 == 0) ? medio * medio : medio * medio * a;
}

Análisis:

• Una llamada recursiva
• Problema se reduce a la mitad
• Trabajo O(1) por nivel

Complejidad: $O(\log n)$

Resumen de complejidades

Consejos para competencias

1. Recursión lineal: Generalmente $O(n)$ o $O(n^2)$
2. División por 2: Generalmente $O(\log n)$
3. Dos llamadas con n-1: Probablemente exponencial
4. Memorización: Reduce a O(número de estados)

Límites prácticos

Ejercicios de análisis

Ejercicio 1

¿Cuál es la complejidad?

void f(int n) {
    if (n <= 1) return;
    f(n - 1);
    f(n - 1);
}

Ver respuesta

$T(n) = 2T(n-1) + O(1)$

Complejidad: $O(2^n)$

Ejercicio 2

¿Cuál es la complejidad?

void f(int n) {
    if (n <= 1) return;
    for (int i = 0; i < n; i++) {
        cout << i << " ";
    }
    f(n / 2);
}

Ver respuesta

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

Por teorema maestro: $a=1$, $b=2$, $f(n)=n$

$n^c = n^0 = 1$, como $f(n) = n = \Omega(n^{0+\epsilon})$, caso 3.

Complejidad: $O(n)$

Siguiente paso

Aplica estos conocimientos en Algoritmos de Ordenamiento.