En la lección anterior aprendimos a contar pasos; en esta aprenderemos a contar memoria. Cerramos 02-01 con una deuda pendiente: aceleramos transbordos de O(n²) a O(n) construyendo un set, y dijimos que el precio era "memoria extra" sin cuantificarlo. La complejidad espacial mide exactamente eso: cuánta memoria adicional necesita un algoritmo en función del tamaño de su entrada. Importa porque la memoria, como el tiempo, es un recurso finito — en un servidor que atiende miles de peticiones de RutaBus simultáneas, un algoritmo que copia la red entera de paradas por petición puede tumbar la máquina aunque sea rapidísimo — y porque, como veremos, tiempo y espacio se pueden intercambiar: a menudo la forma de ganar velocidad es gastar memoria, y conviene saber cuánta.
La buena noticia: el método es el mismo análisis línea a línea de 02-01 y se expresa con la misma notación asintótica de 01-03 (O como cota superior del crecimiento — aquí, del consumo de memoria). Solo cambia la pregunta: en lugar de "¿cuántas veces se ejecuta esta línea?", preguntamos "¿cuánta memoria viva llega a acumular este algoritmo?".
Contenido
- Qué cuenta como espacio: total vs auxiliar
- Análisis línea a línea de memoria
- Copias vs referencias en Python
- El coste espacial de la recursión: la pila de llamadas
- El trade-off tiempo ↔ espacio: un índice de paradas para RutaBus
- Coste espacial de las estructuras de Python
Qué cuenta como espacio: total vs auxiliar
La memoria que usa un algoritmo tiene dos componentes:
- Espacio de entrada: la memoria que ocupan los datos que recibe (la lista de paradas, los horarios...). El algoritmo no puede hacer nada por reducirla: le viene dada.
- Espacio auxiliar: la memoria adicional que el algoritmo reserva para trabajar — variables, estructuras temporales, copias, pila de llamadas.
De ahí salen dos medidas:
| Medida | Qué incluye | Ejemplo: buscar en n paradas con 3 variables |
|---|---|---|
| Espacio total | Entrada + auxiliar | O(n) — domina la entrada |
| Espacio auxiliar | Solo lo que reserva el algoritmo | O(1) — tres variables |
La medida útil para comparar algoritmos es el espacio auxiliar, porque la entrada es igual para todos los algoritmos que resuelven el mismo problema. Cuando digamos "este algoritmo es O(1) en espacio" nos referiremos siempre al espacio auxiliar, y es la convención que usaremos en el resto del curso. (Cuando leas documentación, comprueba cuál de las dos medidas usa: la confusión es frecuente.)
Un matiz más, paralelo al de la lección anterior: el espacio relevante es el máximo simultáneo (el pico), no el acumulado. Si un algoritmo crea una lista temporal de n elementos, la libera y crea otra, su espacio auxiliar es O(n), no O(2n)... que de todos modos sería O(n) — pero el matiz importa cuando las estructuras conviven: dos listas de n elementos vivas a la vez son O(n); una lista de n² elementos es O(n²).
Análisis línea a línea de memoria
Reglas de partida, análogas a las temporales:
- Una variable escalar (un número, un booleano, una referencia a un objeto) ocupa O(1): su tamaño no depende de n.
- Una estructura de datos ocupa proporcionalmente a sus elementos: una lista con n paradas es O(n).
- El espacio auxiliar de un algoritmo es el pico de memoria auxiliar viva durante su ejecución.
Analicemos las funciones de RutaBus que ya conocemos:
def parada_mas_cercana(usuario_x, usuario_y, paradas):
mejor_parada = paradas[0] # O(1): referencia a un dict que YA existe
mejor_distancia = distancia(...) # O(1): un número
for parada in paradas[1:]: # ¡O(n)!: el slice crea una lista nueva
d = distancia(...) # O(1): un número (se reutiliza cada vuelta)
...
return mejor_paradaSorpresa: la función que en tiempo era un limpio O(n) tiene un coste espacial O(n) auxiliar... por culpa del mismo slice que ya nos dio problemas en 02-01. paradas[1:] construye una lista nueva con n−1 referencias. Si iterásemos con índices (for i in range(1, len(paradas))) o con islice, el espacio auxiliar sería O(1): tres variables escalares que se reutilizan en cada vuelta. Fíjate en que d no acumula: en cada iteración sobrescribe su valor anterior, así que cuenta una sola vez.
Segundo ejemplo, la versión con set de la lección anterior:
def transbordos_v2(linea_a, linea_b):
paradas_b = set(linea_b) # O(n): estructura con n elementos
comunes = [] # O(k): crecerá hasta k paradas comunes (k <= n)
for parada in linea_a:
if parada in paradas_b: # O(1) en tiempo... gracias al O(n) en espacio
comunes.append(parada)
return comunesEspacio auxiliar: O(n) por el conjunto + O(k) por el resultado → O(n). Aquí está, ya cuantificada, la factura de la aceleración de 02-01: pasamos de tiempo O(n²) / espacio O(1) a tiempo O(n) / espacio O(n). Ese intercambio tiene nombre y apartado propio más abajo.
Convención: cuando el resultado que se devuelve es necesariamente grande (como
comunes), algunos análisis lo excluyen del espacio auxiliar ("espacio de salida"). Sé consciente de la convención y declárala; en este curso lo incluiremos, salvo aviso.
Copias vs referencias en Python
Para contar memoria en Python hay que saber una cosa fundamental del lenguaje: asignar no es copiar.
linea_l1 = ["Plaza Mayor", "Hospital Central", "Estación Norte", "Parque del Río"]
alias = linea_l1 # O(1): solo una referencia más a LA MISMA lista
copia = list(linea_l1) # O(n): lista nueva con n referencias copiadas
trozo = linea_l1[1:3] # O(k): lista nueva con los k elementos del tramoalias = linea_l1no duplica nada: ambas variables apuntan al mismo objeto (compruébalo:alias is linea_l1→True; si hacesalias.append(...),linea_l1también lo ve). Coste: O(1).list(linea_l1),linea_l1.copy()y los slices crean listas nuevas: O(n) o proporcional al tramo. (Es una copia superficial: se copian las referencias, no los objetos apuntados — suficiente para nuestro análisis de órdenes.)- Pasar una lista como argumento a una función es como una asignación: se pasa la referencia, O(1). Por eso llamar a
parada_mas_cercana(x, y, paradas)no duplica la red; lo que dispara el gasto es lo que la función haga dentro (slices, copias).
| Operación | ¿Crea objeto nuevo? | Coste espacial |
|---|---|---|
b = a |
No (referencia) | O(1) |
| Pasar argumento a función | No (referencia) | O(1) |
a[i], a[i] = v |
No | O(1) |
a[1:], a.copy(), list(a) |
Sí | O(n) |
a + b (listas o strings) |
Sí | O(len(a)+len(b)) |
sorted(a) |
Sí (lista nueva) | O(n) |
a.sort() |
No (ordena en el sitio) | O(1)* auxiliar (*aprox.; el algoritmo real de Python usa algo más) |
La pareja sorted(a) / a.sort() es el ejemplo perfecto de que una misma tarea puede ofrecerse en versión "gasta memoria y conserva el original" o "en el sitio" (in place): elegir bien es análisis espacial aplicado.
El coste espacial de la recursión: la pila de llamadas
En 01-02 vimos que cada llamada recursiva pendiente vive en la pila de llamadas. Eso tiene un coste que el código no muestra: cada llamada activa ocupa un marco (frame) con sus variables locales y la dirección de retorno. Por tanto:
Espacio de una recursión = (profundidad máxima de la pila) × (espacio de cada marco)
Revisitemos contar_paradas_recursivo:
def contar_paradas_recursivo(paradas):
if not paradas:
return 0
return 1 + contar_paradas_recursivo(paradas[1:])Cuando la llamada sobre [] (la más profunda) está ejecutándose, todas las anteriores siguen vivas esperando su resultado para sumarle 1: hay n+1 marcos apilados a la vez. Profundidad O(n) × marco O(1) = O(n) de pila. Y en esta implementación concreta hay más: cada nivel creó su slice paradas[1:], y esa lista sigue viva mientras su marco espera — n listas de tamaños n−1, n−2, ..., 0 conviviendo: suma aritmética → O(n²) auxiliar total. La misma función, medida con las dos varas:
Versión de contar_paradas |
Tiempo (02-01) | Espacio auxiliar |
|---|---|---|
| Iterativa | O(n) | O(1) |
| Recursiva con slices (la nuestra) | O(n²) | O(n²) |
| Recursiva con índice (sin slices) | O(n) | O(n) — solo la pila |
Dos lecciones prácticas:
- Una recursión nunca baja de O(profundidad) en espacio, aunque no cree ninguna estructura: la pila cuenta. Un algoritmo iterativo equivalente suele quedarse en O(1).
- En Python esto no es teórico: la pila tiene un límite (~1000 niveles por defecto;
RecursionError: maximum recursion depth exceededal superarlo).contar_paradas_recursivosobre la red completa de una ciudad con 3.000 paradas ni siquiera termina. Para profundidades pequeñas y acotadas (log n, como en los algoritmos del Módulo 3) la recursión es segura y elegante; para profundidad n sobre entradas grandes, en Python conviene iterar.
El trade-off tiempo ↔ espacio: un índice de paradas para RutaBus
Caso real de RutaBus: la app consulta constantemente los datos de una parada por su nombre (para pintar su ficha, sus horarios, sus correspondencias). Con la lista paradas de siempre, cada consulta es una búsqueda lineal:
def datos_parada(paradas, nombre): # tiempo O(n), espacio O(1)
for parada in paradas:
if parada["nombre"] == nombre:
return parada
return NoneSi la pantalla principal hace 50 consultas y la red tiene 3.000 paradas, son 150.000 comparaciones por usuario y pantalla. La alternativa: precalcular un índice — un diccionario que asocia cada nombre con su parada — una sola vez, y consultar en O(1):
def construir_indice(paradas):
"""Se ejecuta UNA vez al cargar la red. Tiempo O(n), espacio O(n)."""
indice = {}
for parada in paradas:
indice[parada["nombre"]] = parada # referencia, no copia: O(1) por entrada
return indice
indice = construir_indice(paradas)
def datos_parada_v2(indice, nombre): # tiempo O(1), espacio O(1)
return indice.get(nombre) # búsqueda hash: O(1)Comparemos las dos estrategias para q consultas sobre n paradas:
| Estrategia | Preparación | Coste por consulta | q consultas | Memoria extra |
|---|---|---|---|---|
| Búsqueda lineal | — | O(n) | O(q·n) | O(1) |
| Índice (dict) | O(n) una vez | O(1) | O(n + q) | O(n) |
Esto es el trade-off tiempo ↔ espacio en estado puro: hemos comprado velocidad pagando con memoria. Observa que el índice guarda referencias a los mismos diccionarios de la lista (apartado 3): el sobrecoste es una entrada de diccionario por parada, O(n), no una duplicación de todos los datos. ¿Compensa? Casi siempre que q sea grande y n quepa en memoria — que es el caso típico de una app como RutaBus. Pero no es gratis ni automático: en un dispositivo embebido con memoria mínima, o con una red que no cabe en RAM, la búsqueda lineal "lenta pero frugal" puede ser la elección correcta. El análisis espacial existe precisamente para tomar esta decisión con números y no con intuiciones.
Guarda esta idea de "gastar memoria para no repetir trabajo": reaparecerá con nombre propio y a lo grande en la lección 03-03.
Coste espacial de las estructuras de Python
Cierre paralelo al de 02-01: la tabla de referencia, ahora en clave de memoria, para n elementos:
| Estructura | Espacio | Notas prácticas |
|---|---|---|
list |
O(n) | Reserva algo de hueco extra para crecer (constante pequeña) |
tuple |
O(n) | Inmutable; algo más compacta que la lista equivalente |
dict |
O(n) | Guarda clave + valor + tabla hash: mayor constante que una lista |
set |
O(n) | Como el dict, sin valores |
str |
O(n) | Inmutable: cada "modificación" crea uno nuevo (recuerda 02-01) |
| generador | O(1) | Produce los elementos de uno en uno, sin materializar la colección |
La fila estrella es la última. Compara:
cuadrados_lista = [d * d for d in range(1_000_000)] # lista: O(n) — un millón de números en RAM
cuadrados_gen = (d * d for d in range(1_000_000)) # generador: O(1) — una "receta" que los produceLa primera línea materializa el millón de valores; la segunda crea un objeto minúsculo que los va entregando bajo demanda (al iterarlo). Si solo vas a recorrer los valores una vez — sumarlos, buscar el máximo, filtrarlos — el generador da el mismo resultado con espacio auxiliar O(1): sum(d * d for d in range(1_000_000)) nunca tiene el millón de números vivos a la vez. Sus límites: no se puede indexar, ni medir con len, ni recorrer dos veces.
Estas cifras son órdenes de crecimiento; las constantes reales de Python (un int pequeño ocupa 28 bytes, un dict tiene sobrecoste por entrada, etc.) y las técnicas para reducirlas — __slots__, array, procesado en streaming — pertenecen a la lección 05-02 (Uso Eficiente de Memoria). Aquí nos basta con saber qué crece y cómo.
Errores Comunes y Consejos
- Confundir espacio total con auxiliar: "esta función recibe una lista de n paradas, luego es O(n)" — no: la entrada no se le imputa al algoritmo. Pregúntate qué memoria añade él.
- Contar como copia lo que es referencia (y al revés):
b = ay pasar argumentos no copian (O(1));a[1:],a.copy(),a + bysorted(a)sí (O(n)). Este es el error número uno al analizar espacio en Python. - Olvidar la pila de la recursión: una función recursiva "sin variables" no es O(1): cuesta al menos O(profundidad). Y en Python, profundidad n con n grande no es solo cara: es un
RecursionError. - Sumar picos que no coinciden en el tiempo: el espacio auxiliar es el máximo simultáneo. Dos temporales de tamaño n usadas una después de otra siguen siendo O(n).
- Optimizar memoria que no importa: si n son 200 paradas, un índice O(n) es despreciable y el debate es estéril. El análisis espacial decide cuando n es grande o la memoria escasa; si no, prima la claridad del código.
- Consejo: ante un algoritmo, escribe su pareja de costes "tiempo / espacio" (por ejemplo, O(n) / O(1)). Acostumbrarte a verlos juntos te hará detectar trade-offs — y te prepara para leerlos en la documentación de cualquier biblioteca.
Ejercicios
Ejercicio 1. Determina el espacio auxiliar (y de paso el tiempo) de estas dos versiones de una utilidad de RutaBus que comprueba si todas las llegadas de una parada son anteriores a una hora límite:
# Versión A
def todas_antes_a(horarios, limite):
anteriores = [h for h in horarios if h < limite]
return len(anteriores) == len(horarios)
# Versión B
def todas_antes_b(horarios, limite):
for h in horarios:
if h >= limite:
return False
return TrueEjercicio 2. Esta función recursiva calcula la duración total de un trayecto sumando los minutos de cada tramo. Da su coste espacial tal como está escrita, explica de dónde sale, y escribe una versión con espacio auxiliar O(1).
def duracion_total(tramos):
"""tramos: lista de duraciones en minutos, p. ej. [4, 6, 3, 5]."""
if not tramos:
return 0
return tramos[0] + duracion_total(tramos[1:])Ejercicio 3. RutaBus necesita responder muchas consultas del tipo "¿pasa la línea X por la parada Y?". Hoy se resuelve con parada in lineas[x] sobre listas de paradas. Propón una estructura precalculada que responda en O(1), da su coste espacial, y razona en qué escenario no convendría usarla.
Soluciones
Solución 1. La versión A construye con la list comprehension una lista nueva con hasta n horarios: espacio auxiliar O(n) (y tiempo O(n)). La versión B usa una sola variable de bucle que se reutiliza: espacio auxiliar O(1), tiempo O(n) — e incluso mejor en la práctica, porque corta en cuanto encuentra una llegada tardía (esa diferencia entre escenarios la formalizaremos en 02-03). Misma complejidad temporal, distinta espacial: B es estrictamente preferible. Nota: all(h < limite for h in horarios) es la forma idiomática — el generador mantiene el espacio en O(1).
Solución 2. Profundidad de pila: n+1 marcos vivos a la vez → O(n) solo por la pila. Además cada nivel crea el slice tramos[1:] que permanece vivo mientras su marco espera: tamaños n−1, n−2, ..., 0 simultáneos → suma aritmética → O(n²) auxiliar en total (y tiempo O(n²), como vimos en 02-01). Versión iterativa O(1) auxiliar:
def duracion_total_v2(tramos):
total = 0 # O(1)
for minutos in tramos: # la variable se reutiliza en cada vuelta
total += minutos
return total(El sum(tramos) de Python hace exactamente esto.)
Solución 3. Precalcular un diccionario de conjuntos: paradas_por_linea = {"L1": {"Plaza Mayor", ...}, "L2": {...}, ...}. La consulta parada in paradas_por_linea["L1"] es O(1). Coste espacial: una entrada por cada pareja línea-parada → O(L · p) donde L es el número de líneas y p el de paradas por línea — es decir, proporcional al tamaño total de la red, O(n). No convendría si: (a) las consultas son muy escasas (no se amortiza construirlo ni mantenerlo sincronizado cuando la red cambia), o (b) la memoria es el recurso crítico (dispositivo embebido, redes enormes). Es el mismo trade-off tiempo ↔ espacio del índice de paradas: comprar velocidad con memoria solo compensa si la velocidad se usa y la memoria sobra.
Conclusión
Ahora sabemos medir la otra mitad de la factura de un algoritmo. Hemos distinguido espacio total de espacio auxiliar (la medida que compara algoritmos), hemos aplicado el análisis línea a línea a la memoria — escalares O(1), estructuras O(n), y en Python la distinción crucial entre referencias (gratis) y copias (O(n)) —, hemos descubierto que la recursión paga un coste invisible de O(profundidad) en la pila (con RecursionError como recordatorio muy visible en Python), y hemos cuantificado por fin el trade-off tiempo ↔ espacio con el índice de paradas de RutaBus: velocidad O(1) comprada con memoria O(n). La tabla de estructuras — con el generador como campeón del O(1) — completa nuestra caja de herramientas; las técnicas para exprimir la memoria en serio quedan para la lección 05-02.
Con tiempo y espacio ya sabemos rellenar la ficha de costes de cualquier algoritmo... con un matiz pendiente que ha ido asomando toda la lección: hemos dicho "en el peor caso" al medir tiempos, y en los ejercicios nos hemos topado con funciones que a veces terminan a la primera y a veces recorren todo. ¿Qué pasa con los casos favorables? ¿Y con el caso "típico"? ¿Mienten los que dicen que la búsqueda lineal "suele" costar la mitad? En la próxima lección (02-03) pondremos orden: mejor caso, peor caso y caso promedio, cuándo importa cada uno y cómo se relacionan — de verdad — con las notaciones O, Ω y Θ.
Curso de Análisis y Diseño de Algoritmos
Módulo 1: Introducción a los Algoritmos
Módulo 2: Análisis de Algoritmos
- Análisis de Complejidad Temporal
- Análisis de Complejidad Espacial
- Casos de Complejidad: Mejor, Peor y Promedio
Módulo 3: Estrategias de Diseño de Algoritmos
Módulo 4: Algoritmos Clásicos
- Búsqueda Binaria
- Ordenamiento por Inserción
- Ordenamiento por Mezcla (Merge Sort)
- Ordenamiento Rápido (Quick Sort)
- Algoritmo de Dijkstra
- Algoritmo de Floyd-Warshall