A la lliçó anterior vam aprendre a comptar passos; en aquesta aprendrem a comptar memòria. Vam tancar 02-01 amb un deute pendent: vam accelerar transbordaments d'O(n²) a O(n) construint un set, i vam dir que el preu era "memòria extra" sense quantificar-lo. La complexitat espacial mesura exactament això: quanta memòria addicional necessita un algorisme en funció de la mida de la seva entrada. Importa perquè la memòria, com el temps, és un recurs finit — en un servidor que atén milers de peticions de RutaBus simultànies, un algorisme que copia la xarxa sencera de parades per petició pot tombar la màquina encara que sigui rapidíssim — i perquè, com veurem, temps i espai es poden intercanviar: sovint la manera de guanyar velocitat és gastar memòria, i convé saber quanta.
La bona notícia: el mètode és la mateixa anàlisi línia a línia de 02-01 i s'expressa amb la mateixa notació asimptòtica de 01-03 (O com a fita superior del creixement — aquí, del consum de memòria). Només canvia la pregunta: en lloc de "quantes vegades s'executa aquesta línia?", preguntem "quanta memòria viva arriba a acumular aquest algorisme?".
Contingut
- Què compta com a espai: total vs auxiliar
- Anàlisi línia a línia de memòria
- Còpies vs referències en Python
- El cost espacial de la recursió: la pila de crides
- El trade-off temps ↔ espai: un índex de parades per a RutaBus
- Cost espacial de les estructures de Python
Què compta com a espai: total vs auxiliar
La memòria que fa servir un algorisme té dos components:
- Espai d'entrada: la memòria que ocupen les dades que rep (la llista de parades, els horaris...). L'algorisme no hi pot fer res, per reduir-la: li ve donada.
- Espai auxiliar: la memòria addicional que l'algorisme reserva per treballar — variables, estructures temporals, còpies, pila de crides.
D'aquí en surten dues mesures:
| Mesura | Què inclou | Exemple: cercar en n parades amb 3 variables |
|---|---|---|
| Espai total | Entrada + auxiliar | O(n) — domina l'entrada |
| Espai auxiliar | Només el que reserva l'algorisme | O(1) — tres variables |
La mesura útil per comparar algorismes és l'espai auxiliar, perquè l'entrada és igual per a tots els algorismes que resolen el mateix problema. Quan diguem "aquest algorisme és O(1) en espai" ens referirem sempre a l'espai auxiliar, i és la convenció que farem servir a la resta del curs. (Quan llegeixis documentació, comprova quina de les dues mesures fa servir: la confusió és freqüent.)
Un matís més, paral·lel al de la lliçó anterior: l'espai rellevant és el màxim simultani (el pic), no l'acumulat. Si un algorisme crea una llista temporal de n elements, l'allibera i en crea una altra, el seu espai auxiliar és O(n), no O(2n)... que de tota manera seria O(n) — però el matís importa quan les estructures conviuen: dues llistes de n elements vives alhora són O(n); una llista de n² elements és O(n²).
Anàlisi línia a línia de memòria
Regles de partida, anàlogues a les temporals:
- Una variable escalar (un nombre, un booleà, una referència a un objecte) ocupa O(1): la seva mida no depèn de n.
- Una estructura de dades ocupa proporcionalment als seus elements: una llista amb n parades és O(n).
- L'espai auxiliar d'un algorisme és el pic de memòria auxiliar viva durant la seva execució.
Analitzem les funcions de RutaBus que ja coneixem:
def parada_mes_propera(usuari_x, usuari_y, parades):
millor_parada = parades[0] # O(1): referencia a un dict que JA existeix
millor_distancia = distancia(...) # O(1): un nombre
for parada in parades[1:]: # O(n)!: l'slice crea una llista nova
d = distancia(...) # O(1): un nombre (es reutilitza a cada volta)
...
return millor_paradaSorpresa: la funció que en temps era un net O(n) té un cost espacial O(n) auxiliar... per culpa del mateix slice que ja ens va donar problemes a 02-01. parades[1:] construeix una llista nova amb n−1 referències. Si iteréssim amb índexs (for i in range(1, len(parades))) o amb islice, l'espai auxiliar seria O(1): tres variables escalars que es reutilitzen a cada volta. Fixa't que d no acumula: a cada iteració sobreescriu el seu valor anterior, així que compta una sola vegada.
Segon exemple, la versió amb set de la lliçó anterior:
def transbordaments_v2(linia_a, linia_b):
parades_b = set(linia_b) # O(n): estructura amb n elements
comunes = [] # O(k): creixera fins a k parades comunes (k <= n)
for parada in linia_a:
if parada in parades_b: # O(1) en temps... gracies a l'O(n) en espai
comunes.append(parada)
return comunesEspai auxiliar: O(n) pel conjunt + O(k) pel resultat → O(n). Aquí la tenim, ja quantificada, la factura de l'acceleració de 02-01: passem de temps O(n²) / espai O(1) a temps O(n) / espai O(n). Aquest intercanvi té nom i apartat propi més avall.
Convenció: quan el resultat que es retorna és necessàriament gran (com
comunes), algunes anàlisis l'exclouen de l'espai auxiliar ("espai de sortida"). Sigues conscient de la convenció i declara-la; en aquest curs l'inclourem, llevat que avisem del contrari.
Còpies vs referències en Python
Per comptar memòria en Python cal saber una cosa fonamental del llenguatge: assignar no és copiar.
linia_l1 = ["Plaça Major", "Hospital Central", "Estació Nord", "Parc del Riu"]
alies = linia_l1 # O(1): nomes una referencia mes a LA MATEIXA llista
copia = list(linia_l1) # O(n): llista nova amb n referencies copiades
tros = linia_l1[1:3] # O(k): llista nova amb els k elements del tramalies = linia_l1no duplica res: totes dues variables apunten al mateix objecte (comprova-ho:alies is linia_l1→True; si fasalies.append(...),linia_l1també ho veu). Cost: O(1).list(linia_l1),linia_l1.copy()i els slices creen llistes noves: O(n) o proporcional al tram. (És una còpia superficial: es copien les referències, no els objectes apuntats — suficient per a la nostra anàlisi d'ordres.)- Passar una llista com a argument a una funció és com una assignació: es passa la referència, O(1). Per això cridar
parada_mes_propera(x, y, parades)no duplica la xarxa; el que dispara la despesa és el que la funció faci a dins (slices, còpies).
| Operació | Crea un objecte nou? | Cost espacial |
|---|---|---|
b = a |
No (referència) | O(1) |
| Passar un argument a una funció | No (referència) | O(1) |
a[i], a[i] = v |
No | O(1) |
a[1:], a.copy(), list(a) |
Sí | O(n) |
a + b (llistes o strings) |
Sí | O(len(a)+len(b)) |
sorted(a) |
Sí (llista nova) | O(n) |
a.sort() |
No (ordena in situ) | O(1)* auxiliar (*aprox.; l'algorisme real de Python fa servir una mica més) |
La parella sorted(a) / a.sort() és l'exemple perfecte que una mateixa tasca es pot oferir en versió "gasta memòria i conserva l'original" o "in situ" (in place): triar bé és anàlisi espacial aplicada.
El cost espacial de la recursió: la pila de crides
A 01-02 vam veure que cada crida recursiva pendent viu a la pila de crides. Això té un cost que el codi no mostra: cada crida activa ocupa un marc (frame) amb les seves variables locals i l'adreça de retorn. Per tant:
Espai d'una recursió = (profunditat màxima de la pila) × (espai de cada marc)
Revisitem compta_parades_recursiu:
def compta_parades_recursiu(parades):
if not parades:
return 0
return 1 + compta_parades_recursiu(parades[1:])Quan la crida sobre [] (la més profunda) s'està executant, totes les anteriors continuen vives esperant-ne el resultat per sumar-hi 1: hi ha n+1 marcs apilats alhora. Profunditat O(n) × marc O(1) = O(n) de pila. I en aquesta implementació concreta encara hi ha més: cada nivell va crear el seu slice parades[1:], i aquesta llista continua viva mentre el seu marc espera — n llistes de mides n−1, n−2, ..., 0 convivint: suma aritmètica → O(n²) auxiliar total. La mateixa funció, mesurada amb les dues vares:
Versió de compta_parades |
Temps (02-01) | Espai auxiliar |
|---|---|---|
| Iterativa | O(n) | O(1) |
| Recursiva amb slices (la nostra) | O(n²) | O(n²) |
| Recursiva amb índex (sense slices) | O(n) | O(n) — només la pila |
Dues lliçons pràctiques:
- Una recursió mai no baixa d'O(profunditat) en espai, encara que no creï cap estructura: la pila compta. Un algorisme iteratiu equivalent sol quedar-se en O(1).
- En Python això no és teòric: la pila té un límit (~1000 nivells per defecte;
RecursionError: maximum recursion depth exceededen superar-lo).compta_parades_recursiusobre la xarxa completa d'una ciutat amb 3.000 parades ni tan sols acaba. Per a profunditats petites i acotades (log n, com en els algorismes del Mòdul 3) la recursió és segura i elegant; per a profunditat n sobre entrades grans, en Python convé iterar.
El trade-off temps ↔ espai: un índex de parades per a RutaBus
Cas real de RutaBus: l'app consulta constantment les dades d'una parada pel seu nom (per pintar-ne la fitxa, els horaris, les correspondències). Amb la llista parades de sempre, cada consulta és una cerca lineal:
def dades_parada(parades, nom): # temps O(n), espai O(1)
for parada in parades:
if parada["nom"] == nom:
return parada
return NoneSi la pantalla principal fa 50 consultes i la xarxa té 3.000 parades, són 150.000 comparacions per usuari i pantalla. L'alternativa: precalcular un índex — un diccionari que associa cada nom amb la seva parada — una sola vegada, i consultar en O(1):
def construeix_index(parades):
"""S'executa UNA vegada en carregar la xarxa. Temps O(n), espai O(n)."""
index = {}
for parada in parades:
index[parada["nom"]] = parada # referencia, no copia: O(1) per entrada
return index
index = construeix_index(parades)
def dades_parada_v2(index, nom): # temps O(1), espai O(1)
return index.get(nom) # cerca hash: O(1)Comparem les dues estratègies per a q consultes sobre n parades:
| Estratègia | Preparació | Cost per consulta | q consultes | Memòria extra |
|---|---|---|---|---|
| Cerca lineal | — | O(n) | O(q·n) | O(1) |
| Índex (dict) | O(n) una vegada | O(1) | O(n + q) | O(n) |
Això és el trade-off temps ↔ espai en estat pur: hem comprat velocitat pagant amb memòria. Observa que l'índex guarda referències als mateixos diccionaris de la llista (apartat 3): el sobrecost és una entrada de diccionari per parada, O(n), no una duplicació de totes les dades. Compensa? Gairebé sempre que q sigui gran i n càpiga en memòria — que és el cas típic d'una app com RutaBus. Però no és gratuït ni automàtic: en un dispositiu encastat amb memòria mínima, o amb una xarxa que no cap a la RAM, la cerca lineal "lenta però frugal" pot ser l'elecció correcta. L'anàlisi espacial existeix precisament per prendre aquesta decisió amb números i no amb intuïcions.
Guarda't aquesta idea de "gastar memòria per no repetir feina": reapareixerà amb nom propi i a gran escala a la lliçó 03-03.
Cost espacial de les estructures de Python
Tancament paral·lel al de 02-01: la taula de referència, ara en clau de memòria, per a n elements:
| Estructura | Espai | Notes pràctiques |
|---|---|---|
list |
O(n) | Reserva una mica d'espai extra per créixer (constant petita) |
tuple |
O(n) | Immutable; una mica més compacta que la llista equivalent |
dict |
O(n) | Guarda clau + valor + taula hash: constant més gran que una llista |
set |
O(n) | Com el dict, sense valors |
str |
O(n) | Immutable: cada "modificació" en crea un de nou (recorda 02-01) |
| generador | O(1) | Produeix els elements d'un en un, sense materialitzar la col·lecció |
La fila estrella és l'última. Compara:
quadrats_llista = [d * d for d in range(1_000_000)] # llista: O(n) — un milio de nombres a la RAM
quadrats_gen = (d * d for d in range(1_000_000)) # generador: O(1) — una "recepta" que els produeixLa primera línia materialitza el milió de valors; la segona crea un objecte minúscul que els va lliurant sota demanda (en iterar-lo). Si només has de recórrer els valors una vegada — sumar-los, buscar-ne el màxim, filtrar-los — el generador dona el mateix resultat amb espai auxiliar O(1): sum(d * d for d in range(1_000_000)) mai no té el milió de nombres vius alhora. Els seus límits: no es pot indexar, ni mesurar amb len, ni recórrer dues vegades.
Aquestes xifres són ordres de creixement; les constants reals de Python (un int petit ocupa 28 bytes, un dict té un sobrecost per entrada, etc.) i les tècniques per reduir-les — __slots__, array, processament en streaming — pertanyen a la lliçó 05-02 (Ús Eficient de Memòria). Aquí en tenim prou de saber què creix i com.
Errors Comuns i Consells
- Confondre espai total amb auxiliar: "aquesta funció rep una llista de n parades, per tant és O(n)" — no: l'entrada no se li imputa a l'algorisme. Pregunta't quina memòria hi afegeix ell.
- Comptar com a còpia el que és referència (i a l'inrevés):
b = ai passar arguments no copien (O(1));a[1:],a.copy(),a + bisorted(a)sí (O(n)). Aquest és l'error número u en analitzar espai en Python. - Oblidar la pila de la recursió: una funció recursiva "sense variables" no és O(1): costa com a mínim O(profunditat). I en Python, profunditat n amb n gran no és només cara: és un
RecursionError. - Sumar pics que no coincideixen en el temps: l'espai auxiliar és el màxim simultani. Dues temporals de mida n usades l'una després de l'altra continuen sent O(n).
- Optimitzar memòria que no importa: si n són 200 parades, un índex O(n) és menyspreable i el debat és estèril. L'anàlisi espacial decideix quan n és gran o la memòria escasseja; si no, preval la claredat del codi.
- Consell: davant d'un algorisme, escriu la seva parella de costos "temps / espai" (per exemple, O(n) / O(1)). Acostumar-te a veure'ls junts et farà detectar trade-offs — i et prepara per llegir-los a la documentació de qualsevol biblioteca.
Exercicis
Exercici 1. Determina l'espai auxiliar (i de passada el temps) d'aquestes dues versions d'una utilitat de RutaBus que comprova si totes les arribades d'una parada són anteriors a una hora límit:
# Versio A
def totes_abans_a(horaris, limit):
anteriors = [h for h in horaris if h < limit]
return len(anteriors) == len(horaris)
# Versio B
def totes_abans_b(horaris, limit):
for h in horaris:
if h >= limit:
return False
return TrueExercici 2. Aquesta funció recursiva calcula la durada total d'un trajecte sumant els minuts de cada tram. Dona el seu cost espacial tal com està escrita, explica d'on surt, i escriu una versió amb espai auxiliar O(1).
def durada_total(trams):
"""trams: llista de durades en minuts, p. ex. [4, 6, 3, 5]."""
if not trams:
return 0
return trams[0] + durada_total(trams[1:])Exercici 3. RutaBus necessita respondre moltes consultes del tipus "passa la línia X per la parada Y?". Avui es resol amb parada in linies[x] sobre llistes de parades. Proposa una estructura precalculada que respongui en O(1), dona el seu cost espacial, i raona en quin escenari no convindria fer-la servir.
Solucions
Solució 1. La versió A construeix amb la list comprehension una llista nova amb fins a n horaris: espai auxiliar O(n) (i temps O(n)). La versió B fa servir una sola variable de bucle que es reutilitza: espai auxiliar O(1), temps O(n) — i fins i tot millor a la pràctica, perquè talla així que troba una arribada tardana (aquesta diferència entre escenaris la formalitzarem a 02-03). Mateixa complexitat temporal, diferent espacial: B és estrictament preferible. Nota: all(h < limit for h in horaris) és la forma idiomàtica — el generador manté l'espai en O(1).
Solució 2. Profunditat de pila: n+1 marcs vius alhora → O(n) només per la pila. A més, cada nivell crea l'slice trams[1:], que roman viu mentre el seu marc espera: mides n−1, n−2, ..., 0 simultànies → suma aritmètica → O(n²) auxiliar en total (i temps O(n²), com vam veure a 02-01). Versió iterativa O(1) auxiliar:
def durada_total_v2(trams):
total = 0 # O(1)
for minuts in trams: # la variable es reutilitza a cada volta
total += minuts
return total(El sum(trams) de Python fa exactament això.)
Solució 3. Precalcular un diccionari de conjunts: parades_per_linia = {"L1": {"Plaça Major", ...}, "L2": {...}, ...}. La consulta parada in parades_per_linia["L1"] és O(1). Cost espacial: una entrada per cada parella línia-parada → O(L · p) on L és el nombre de línies i p el de parades per línia — és a dir, proporcional a la mida total de la xarxa, O(n). No convindria si: (a) les consultes són molt escasses (no s'amortitza construir-lo ni mantenir-lo sincronitzat quan la xarxa canvia), o (b) la memòria és el recurs crític (dispositiu encastat, xarxes enormes). És el mateix trade-off temps ↔ espai de l'índex de parades: comprar velocitat amb memòria només compensa si la velocitat es fa servir i la memòria sobra.
Conclusió
Ara sabem mesurar l'altra meitat de la factura d'un algorisme. Hem distingit espai total d'espai auxiliar (la mesura que compara algorismes), hem aplicat l'anàlisi línia a línia a la memòria — escalars O(1), estructures O(n), i en Python la distinció crucial entre referències (gratuïtes) i còpies (O(n)) —, hem descobert que la recursió paga un cost invisible d'O(profunditat) a la pila (amb RecursionError com a recordatori ben visible en Python), i hem quantificat per fi el trade-off temps ↔ espai amb l'índex de parades de RutaBus: velocitat O(1) comprada amb memòria O(n). La taula d'estructures — amb el generador com a campió de l'O(1) — completa la nostra caixa d'eines; les tècniques per esprémer la memòria de debò queden per a la lliçó 05-02.
Amb temps i espai ja sabem omplir la fitxa de costos de qualsevol algorisme... amb un matís pendent que ha anat traient el cap tota la lliçó: hem dit "en el pitjor cas" en mesurar temps, i als exercicis hem topat amb funcions que de vegades acaben a la primera i de vegades ho recorren tot. Què passa amb els casos favorables? I amb el cas "típic"? Menteixen, els qui diuen que la cerca lineal "sol" costar la meitat? A la propera lliçó (02-03) hi posarem ordre: millor cas, pitjor cas i cas mitjà, quan importa cadascun i com es relacionen — de debò — amb les notacions O, Ω i Θ.
Curs d'Anàlisi i Disseny d'Algorismes
Mòdul 1: Introducció als Algorismes
Mòdul 2: Anàlisi d'Algorismes
- Anàlisi de Complexitat Temporal
- Anàlisi de Complexitat Espacial
- Casos de Complexitat: Millor, Pitjor i Mitjà
Mòdul 3: Estratègies de Disseny d'Algorismes
Mòdul 4: Algorismes Clàssics
- Cerca Binària
- Ordenació per Inserció
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorisme de Dijkstra
- Algorisme de Floyd-Warshall