Ejercicios Prácticos de Complejidad Algorítmica II

Esta segunda sesión de ejercicios prácticos se centra en el análisis de complejidad espacial (consumo de memoria dinámica en el Heap y marco de llamadas en el Stack) y en algoritmos recursivos frente a iterativos.

1. Claves para el Análisis de Complejidad Espacial #

La complejidad espacial evalúa la memoria adicional que requiere un algoritmo en función del tamaño de entrada $n$:

• Espacio Constante ($O(1)$): Variables escalares auxiliares (int sum = 0;, punteros simples) independientemente de $n$.
• Espacio Lineal ($O(n)$): Creación de nuevos arrays, listas o estructuras proporcionales a $n$, o bien $n$ llamadas recursivas activas en la pila de ejecución (Call Stack).
• Espacio Exponencial ($O(2^n)$ o $O(n^2)$): Árboles recursivos profundos sin poda o matrices bidimensionales $n \times n$.

2. Comparativa: Recursión Clásica vs Optimización Iterativa #

1# Caso 1: Fibonacci recursivo ingenuo -> Tiempo O(2^n), Espacio Stack O(n)
2def fibonacci_recursivo(n):
3    if n <= 1:
4        return n
5    return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n - 2)
6
7  # Caso 2: Fibonacci iterativo optimizado -> Tiempo O(n), Espacio O(1)
8def fibonacci_iterativo(n):
9    if n <= 1:
10        return n
11    a, b = 0, 1
12    for _ in range(2, n + 1):
13        a, b = b, a + b
14    return b