Complejidad de algoritmos recursivos

5.1 Análisis de la complejidad de los algoritmos recursivos.

Los algoritmos recursivos son una herramienta poderosa para resolver tareas complicadas, permitiendo descomponerlas en subproblemas más sencillos. Sin embargo, el análisis de la complejidad de los algoritmos recursivos puede ser más complicado en comparación con los algoritmos iterativos. Los aspectos principales que se deben considerar al analizar algoritmos recursivos incluyen la complejidad temporal y espacial.

Estas estimaciones muestran cuánto tiempo y memoria se requieren para ejecutar el algoritmo en función del tamaño de los datos de entrada. El análisis de la complejidad de algoritmos recursivos a menudo incluye la construcción y resolución de ecuaciones recurrentes, que describen el comportamiento del algoritmo.

Complejidad temporal de los algoritmos recursivos:

La complejidad temporal de los algoritmos recursivos a menudo se analiza usando relaciones recurrentes, que describen el tiempo de ejecución del algoritmo en términos del tiempo de ejecución de sus llamadas recursivas.

Ecuación recurrente:

La ecuación recurrente es una ecuación que expresa la complejidad temporal del algoritmo en términos de su complejidad temporal para tamaños de entrada más pequeños. Ayuda a describir los costos temporales de ejecutar un algoritmo recursivo.

Ejemplos:

• T(n) = T(n − 1) + O(1)
• T(n) = 2T(2n) + O(n)

5.2 Ejemplos de problemas con algoritmos recursivos.

Ejemplo 1: Factorial de un número

Consideremos un algoritmo para calcular el factorial del número n:

def factorial(n):
    if n == 0:
        # Caso base: el factorial de 0 es 1
        return 1
    else:
        # Llamada recursiva
        return n * factorial(n - 1)
        

La relación recurrente para este algoritmo se puede escribir como:

T(n) = T(n − 1) + O(1)

La solución de esta ecuación es:

T(n) = O(n)

Por lo tanto, la complejidad temporal del algoritmo factorial es O(n).

Ejemplo 2: Ordenamiento rápido

Consideremos el algoritmo de ordenamiento rápido:

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]

    left = [x for x in arr if x < pivot]

    middle = [x for x in arr if x == pivot]

    right = [x for x in arr if x > pivot]

    return quicksort(left) + middle + quicksort(right)
        

La relación recurrente para este algoritmo en el caso promedio:

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

La solución de esta ecuación utilizando el método maestro es

• T(n) = O(n * log(n))

5.3 Complejidad espacial de los algoritmos recursivos

La complejidad espacial de los algoritmos recursivos se determina como la suma de la memoria utilizada para almacenar variables y la memoria utilizada para la pila de llamadas. En algoritmos recursivos profundos, se puede usar una cantidad significativa de memoria para almacenar el contexto de las llamadas.

Ejemplo: Fibonacci

Consideremos el algoritmo para calcular los números de Fibonacci:

def fibonacci(n):
    if n <= 1:
        # Caso base
        return n
    else:
        # Llamada recursiva
        return fibonacci(n - 1) + fibonacci(n - 2)
        

La relación recurrente para la complejidad temporal:

• T(n) = T(n − 1) + T(n − 2) + O(1)

La solución de esta ecuación es:

• T(n) = O(2n)

La complejidad espacial se determina por la máxima profundidad de las llamadas recursivas, que en este caso es O(n).

5.4 Métodos de análisis de la complejidad de los algoritmos recursivos

Métodos de análisis de la complejidad de los algoritmos recursivos

1. Método de sustitución:
• Se utiliza para suponer la forma de la solución y probar por inducción.
• Ejemplo: Sustitución para resolver ecuaciones recurrentes.
2. 2. Método del árbol de recursión:
   • Visualización de las llamadas recursivas en forma de árbol, donde cada nodo representa una llamada a función.
   • Ejemplo: Ordenamiento rápido con llamadas recursivas.
3. Método maestro:
   • Patrón para analizar ecuaciones recurrentes del tipo: T(n) = a * T(n / b) + f(n)
   • Ejemplo: Ordenamiento rápido.

El análisis de la complejidad de los algoritmos recursivos requiere considerar tanto la complejidad temporal como la espacial. Comprender las relaciones recurrentes y aplicar métodos de análisis, como la sustitución, el método del árbol de recursión y el método maestro, ayudan a evaluar con precisión el rendimiento de los algoritmos recursivos.