El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Anàlisi de Complexitat

Següent ►
►

A la lliçó anterior vam aprendre a expressar costos amb la notació asimptòtica; en aquesta aprendrem a calcular-los. L'anàlisi de complexitat és l'habilitat de mirar un algorisme —o directament el seu codi— i determinar, sense executar-lo, com creixeran el seu temps i la seva memòria amb la mida de l'entrada. És una habilitat d'enginyeria de primer ordre: permet descartar dissenys inviables abans d'escriure una línia i localitzar colls d'ampolla llegint codi.

Continuem amb Rutalia. El seu equip ha heretat un backend amb funcions que "de sobte" van lentes ara que hi ha un milió de comandes: cercar una comanda per identificador, detectar comandes duplicades, registrar lliuraments en una llista que no para de créixer. En aquesta lliçó analitzarem aquestes funcions una per una i posarem números a la intuïció.

Contingut

  1. Complexitat temporal i espacial: què mesurem exactament
  2. Recompte d'operacions i regles bàsiques
  3. Bucles: simples, imbricats i dependents
  4. Millor cas, pitjor cas i cas mitjà
  5. Anàlisi amortitzada: la llista dinàmica
  6. Recurrències i teorema mestre (introducció)

  1. Complexitat temporal i espacial: què mesurem exactament

Donat un algorisme i una entrada de mida n, definim:

  • Complexitat temporal T(n): nombre d'operacions elementals (en el model RAM de la lliçó 01-01) que executa l'algorisme.
  • Complexitat espacial S(n): quantitat de memòria addicional que necessita, sense comptar l'entrada. També s'anomena espai auxiliar.
Concepte Què compta Exemple Rutalia
Temporal operacions executades comparacions en cercar una comanda
Espacial (auxiliar) memòria extra reservada un set amb els IDs ja vistos
Espacial (total) entrada + auxiliar la llista de comandes + el set

Un matís que sovint passa desapercebut: l'espai auxiliar inclou també la pila de crides de les funcions recursives (cada crida pendent ocupa memòria). Ho veurem en detall a la lliçó 01-03.

Sovint temps i espai s'intercanvien: gastar més memòria (per exemple, un índex auxiliar) pot reduir dràsticament el temps. Bona part de l'enginyeria d'algorismes consisteix a triar bé aquest equilibri.

  1. Recompte d'operacions i regles bàsiques

El mètode fonamental és directe: per a cada línia, determinar (a) quant costa executar-la un cop i (b) quantes vegades s'executa. El cost total és la suma de tots els productes. Després se simplifica amb la notació asimptòtica.

Analitzem la cerca lineal d'una comanda a Rutalia:

def cercar_comanda(comandes, id_cercat):
    """Retorna la comanda amb aquest id, o None si no existeix."""
    for comanda in comandes:            # s'executa fins a n vegades
        if comanda["id"] == id_cercat:  # 1 comparació per volta
            return comanda              # com a molt 1 vegada
    return None                         # com a molt 1 vegada

Recompte en el pitjor cas (la comanda no hi és): el bucle fa n voltes amb un cost constant c per volta, més un cost constant final. T(n) = c·n + c' = Θ(n). Espai auxiliar: només la variable del bucle → S(n) = Θ(1).

Regles de composició que farem servir constantment:

  • Seqüència: els blocs consecutius es sumen. Θ(n) + Θ(n²) = Θ(n²) (domina el més gran).
  • Bucle: cost del cos multiplicat pel nombre d'iteracions.
  • Condicional: en el pitjor cas, el cost de la branca més cara (més la condició).
  • Crida a funció: el cost de la funció cridada (no costa 1 pel fet de ser una línia!).

I el recordatori de la lliçó anterior: en Python, x in llista és Θ(n), llista.insert(0, x) és Θ(n), sorted(llista) és Θ(n log n), un slice llista[a:b] és Θ(b−a). Comptar "línies" en lloc d'operacions reals és la font clàssica d'anàlisis errònies.

  1. Bucles: simples, imbricats i dependents

3.1 Bucles simples

Un bucle que fa n voltes amb un cos constant és Θ(n). Si el cos costa f(n), el total és n · f(n).

3.2 Bucles imbricats independents

Els costos es multipliquen. Versió ingènua del detector de comandes duplicades de Rutalia (dos clients que demanen el mateix a la mateixa adreça):

def detectar_duplicats_v1(comandes):
    """Retorna parelles d'índexs de comandes idèntiques. Versió ingènua."""
    duplicats = []
    n = len(comandes)
    for i in range(n):                      # n voltes
        for j in range(i + 1, n):           # n-1, n-2, ..., 1, 0 voltes
            if (comandes[i]["adreca"] == comandes[j]["adreca"]
                    and comandes[i]["article"] == comandes[j]["article"]):
                duplicats.append((i, j))
    return duplicats

El bucle interior no fa sempre n voltes: en fa n−1 la primera vegada, n−2 la segona… És un bucle dependent (depèn d'i). El total d'iteracions és:

(n−1) + (n−2) + ... + 1 + 0 = n(n−1)/2 = Θ(n²)

Aquesta suma aritmètica apareix constantment; convé memoritzar-ne el resultat: un doble bucle triangular és quadràtic, igual que el doble bucle complet n·n (la meitat de feina no canvia l'ordre). Amb un milió de comandes: ~5·10¹¹ comparacions. Aquest és, literalment, el procés que trigava hores a Rutalia.

L'alternativa amb memòria auxiliar:

def detectar_duplicats_v2(comandes):
    """Versió amb conjunt auxiliar: temps Θ(n), espai Θ(n)."""
    vistos = {}          # clau -> primer índex on va aparèixer
    duplicats = []
    for i, comanda in enumerate(comandes):            # n voltes
        clau = (comanda["adreca"], comanda["article"])
        if clau in vistos:                            # O(1) en un dict (mitjana)
            duplicats.append((vistos[clau], i))
        else:
            vistos[clau] = i                          # O(1) (mitjana)
    return duplicats

Temps Θ(n) a canvi d'espai auxiliar Θ(n): un intercanvi temps/memòria de manual. (Per què el dict aconsegueix O(1) per operació ho veurem a la lliçó 01-04.)

3.3 Bucles amb pas multiplicatiu

Quan la variable de control es multiplica o es divideix a cada volta, el nombre d'iteracions és logarítmic:

def nivells_de_zoom(n_paquets):
    """Quantes vegades podem partir la zona de repartiment per la meitat?"""
    nivells = 0
    while n_paquets > 1:
        n_paquets //= 2      # es divideix entre 2 a cada volta
        nivells += 1
    return nivells           # ≈ log2(n) voltes → Θ(log n)

Resum de patrons:

Patró de bucle Iteracions Ordre
for i in range(n) n Θ(n)
doble bucle complet n × n n² Θ(n²)
doble bucle triangular (j des d'i+1) n(n−1)/2 Θ(n²)
while dividint entre 2 log₂ n Θ(log n)
bucle Θ(n) amb cos Θ(log n) n·log n Θ(n log n)

  1. Millor cas, pitjor cas i cas mitjà

Per a un mateix n, entrades diferents poden costar diferent. Definim tres funcions:

  • Pitjor cas T_pitjor(n): cost màxim sobre totes les entrades de mida n. És la mètrica per defecte: dona una garantia.
  • Millor cas T_millor(n): cost mínim. Gairebé mai no és útil per si sol (qualsevol algorisme amb sortida anticipada té un bon millor cas).
  • Cas mitjà T_mitja(n): cost esperat sota una distribució d'entrades. És el més realista i el més difícil: exigeix assumir una distribució.

Per a cercar_comanda (cerca lineal), suposant que la comanda cercada hi és i que és igualment probable que sigui a qualsevol posició:

Cas Situació Cost
Millor la comanda és la primera Θ(1)
Pitjor és l'última o no hi és Θ(n)
Mitjà posició uniforme a l'atzar (1+2+...+n)/n = (n+1)/2 → Θ(n)

Fixa-t'hi: el cas mitjà continua sent lineal; "de mitjana miro la meitat de la llista" no canvia l'ordre de creixement. I recorda l'advertiment de 01-01: millor/pitjor/mitjà són funcions diferents, i a cadascuna se li poden aplicar O, Ω o Θ. "El pitjor cas de la cerca lineal és Θ(n)" és una afirmació completa i correcta.

A Rutalia això té una lectura operativa: per al quadre de comandament intern pot bastar un bon cas mitjà; per al càlcul de rutes que ha de respondre abans que les furgonetes surtin a les 8:00, el que importa és la garantia del pitjor cas.

  1. Anàlisi amortitzada: la llista dinàmica

Hi ha estructures les operacions de les quals són gairebé sempre barates però de tant en tant cares. Jutjar-les pel seu pitjor cas puntual és enganyós; el que és honest és repartir el cost: això és l'anàlisi amortitzada. El cost amortitzat d'una operació és el cost total d'una seqüència de m operacions dividit entre m.

L'exemple canònic és la llista dinàmica —exactament el que fa el list.append de Python—. Rutalia registra cada lliurament del dia en una llista:

lliuraments = []
def registrar_lliurament(lliurament):
    lliuraments.append(lliurament)   # quant costa, això?

Internament, la llista reserva un array amb una certa capacitat. Mentre queda lloc, append escriu a la posició següent: cost 1. Quan l'array s'omple, se'n reserva un altre (típicament del doble de mida), es copien els k elements existents i després s'escriu: cost k+1.

Quant costen n appends començant de buit, amb duplicació de capacitat? Les còpies passen en omplir-se les capacitats 1, 2, 4, 8, …, i copien aquest nombre d'elements:

cost total ≤ n (escriptures) + (1 + 2 + 4 + ... + n) (còpies) ≤ n + 2n = 3n

Per tant el cost amortitzat per append és 3n / n = 3 = Θ(1), encara que un append concret pugui costar Θ(n). Aquesta és la tècnica agregada; n'hi ha d'altres de més fines (mètode del banquer, del potencial) que no necessitarem en aquest curs.

graph LR
    subgraph "Cost per append (n = 1..8)"
    A["1"] --> B["2 (copia 1)"] --> C["3 (copia 2)"] --> D["1"] --> E["5 (copia 4)"] --> F["1"] --> G["1"] --> H["1"]
    end

Dues conseqüències pràctiques per a Rutalia:

  • Registrar el milió de lliuraments del dia amb append costa Θ(n) en total: perfecte.
  • Compte amb l'operació "cosina": lliuraments.insert(0, x) (inserir al principi) desplaça tots els elements i costa Θ(n) cada vegada, no amortitzat. Un milió d'insercions al principi és Θ(n²). Si cal inserir pels dos extrems, l'estructura adequada és una altra (collections.deque, que apareixerà a la lliçó 01-04).

  1. Recurrències i teorema mestre (introducció)

Quan un algorisme es resol cridant-se a si mateix sobre entrades més petites, el seu cost s'expressa com una recurrència: una equació on T(n) depèn de T sobre mides menors. Aquí només necessitem el mínim per analitzar algorismes de divideix i venceràs; el disseny d'algorismes recursius com a tècnica és el tema de la lliçó 01-03.

Exemple: Rutalia guarda les adreces de lliurament ordenades alfabèticament i cerca amb el clàssic "obrir per la meitat" (la cerca binària en si s'estudia a fons a 04-01; aquí només ens interessa el seu cost). Cada pas descarta la meitat de les adreces amb una feina constant:

T(n) = T(n/2) + c

Desplegant: T(n) = T(n/4) + 2c = T(n/8) + 3c = ... = T(1) + c·log₂ n = Θ(log n).

Per a les recurrències del tipus divideix i venceràs existeix una recepta general, el teorema mestre. Per a recurrències de la forma:

T(n) = a · T(n/b) + f(n) amb a ≥ 1 subproblemes de mida n/b i cost f(n) de dividir/combinar

es compara f(n) amb n^(log_b a):

Cas Condició Resultat Exemple
1 f(n) creix menys que n^(log_b a) T(n) = Θ(n^(log_b a)) T(n)=2T(n/2)+1 → Θ(n)
2 f(n) = Θ(n^(log_b a)) T(n) = Θ(n^(log_b a) · log n) T(n)=2T(n/2)+n → Θ(n log n)
3 f(n) creix més (amb condició tècnica de regularitat) T(n) = Θ(f(n)) T(n)=2T(n/2)+n² → Θ(n²)

Comprovacions ràpides:

  • Cerca binària: a=1, b=2 → n^(log₂ 1) = n⁰ = 1; f(n)=Θ(1) coincideix → cas 2 → Θ(log n). ✔
  • Ordenació per mescla (que veurem com a esquema a 01-03 i en detall a 04-02): a=2, b=2, f(n)=Θ(n) → n^(log₂ 2) = n coincideix → cas 2 → Θ(n log n). ✔

A nivell introductori n'hi ha prou amb això: identificar a, b i f(n), calcular n^(log_b a) i triar el cas. Quan la recurrència no encaixi en el patró (per exemple T(n) = T(n−1) + n, que dona Θ(n²)), sempre queda el mètode de desplegar la recurrència a mà, com hem fet amb la cerca binària.

Errors Comuns i Consells

  • Comptar línies en lloc d'operacions. Una línia amb sorted(...), in llista o un slice amaga costos Θ(n log n) o Θ(n). Abans de comptar, pregunta't què fa per dins cada expressió.
  • Multiplicar bucles imbricats a cegues. Si el bucle interior depèn de l'exterior, cal sumar la sèrie. De vegades la suma dona menys de l'esperat: dos bucles imbricats on l'interior avança un punter global (patró "dos punters") poden ser Θ(n) en total, no Θ(n²).
  • Confondre amortitzat amb cas mitjà. El cost amortitzat és una garantia sobre qualsevol seqüència d'operacions (no hi ha probabilitat); el cas mitjà depèn d'una distribució d'entrades suposada. append és O(1) amortitzat sempre; la cerca lineal és Θ(n) de mitjana si la posició és uniforme.
  • Oblidar l'espai. Un algorisme elegant en temps pot ser inviable per memòria (p. ex. materialitzar totes les parelles de comandes: Θ(n²) d'espai amb n = 10⁶ és de l'ordre de terabytes). Analitza sempre les dues dimensions.
  • Aplicar el teorema mestre on no toca. Requereix subproblemes de mida n/b (fracció constant). T(n) = T(n−1) + c no és divideix i venceràs; es desplega a mà (dona Θ(n)).
  • Consell: verifica empíricament. Mesura el temps amb time.perf_counter() per a n, 2n i 4n: si el temps es multiplica per ~4 en duplicar n, tens alguna cosa quadràtica al davant. La mesura no substitueix l'anàlisi, però la confirma o la desmenteix en minuts.

Exercicis

Exercici 1: Analitzar tres fragments

Determina la complexitat temporal (pitjor cas, en Θ) de cada funció, justificant el recompte:

def a(comandes):
    total = 0
    for c in comandes:
        total += c["pes"]
    for c in comandes:
        total -= c["descompte"]
    return total

def b(comandes):
    resultat = []
    for c in comandes:
        if c["urgent"]:
            resultat = resultat + [c]   # compte amb aquesta línia!
    return resultat

def c(zones, comandes):   # z zones, n comandes
    assignacions = []
    for zona in zones:
        for c in comandes:
            if c["cp"] == zona["cp"]:
                assignacions.append((zona["id"], c["id"]))
    return assignacions

Exercici 2: Millor, pitjor i mitjà a Rutalia

La funció següent comprova si un codi de descompte és a la llista de codis vàlids (no ordenada, sense duplicats, n codis). Suposant que quan el codi és vàlid la seva posició és uniforme a l'atzar, i que el 50 % de les comprovacions són de codis invàlids, calcula el millor cas, el pitjor cas i el cas mitjà.

def codi_valid(codis, codi):
    for c in codis:
        if c == codi:
            return True
    return False

Exercici 3: Recurrències

Resol amb el teorema mestre (o desplegant, si no s'hi pot aplicar):

  1. T(n) = 4·T(n/2) + n
  2. T(n) = T(n/2) + n
  3. T(n) = T(n−1) + c

Solucions

Solució 1

  • a: dos bucles Θ(n) en seqüència (no imbricats): Θ(n) + Θ(n) = Θ(n).
  • b: la trampa és a resultat = resultat + [c], que crea una llista nova copiant els k elements acumulats: cost Θ(k) a la volta k. En el pitjor cas (totes urgents): 1 + 2 + ... + n = Θ(n²). Amb resultat.append(c) (amortitzat O(1)) seria Θ(n). Una sola línia marca la diferència entre 0,01 s i hores amb un milió de comandes.
  • c: bucles imbricats independents: z voltes × n voltes de feina constant = Θ(z·n). Amb dues variables de mida, la resposta ha d'incloure totes dues; dir "Θ(n²)" seria incorrecte llevat que z ≈ n.

Solució 2

  • Millor cas: el codi és el primer → Θ(1).
  • Pitjor cas: codi invàlid (o l'últim) → n comparacions → Θ(n).
  • Cas mitjà: amb probabilitat 1/2 el codi és invàlid (n comparacions); amb probabilitat 1/2 és vàlid i de mitjana en mira (n+1)/2. Cost mitjà = ½·n + ½·(n+1)/2 = 3n/4 + 1/4 → Θ(n). Com sempre en la cerca lineal, el cas mitjà no baixa de l'ordre lineal.

Solució 3

  1. a=4, b=2, f(n)=n. n^(log₂ 4) = n², i f(n)=n creix menys → cas 1 → Θ(n²).
  2. a=1, b=2, f(n)=n. n^(log₂ 1) = 1, i f(n)=n creix més (i compleix la regularitat) → cas 3 → Θ(n). Intuïció: el primer nivell ja costa n, i els següents n/2, n/4… sumen menys de 2n.
  3. No s'hi aplica el teorema mestre (el subproblema és n−1, no una fracció de n). Desplegant: c + c + ... + c, n vegades → Θ(n).

Conclusió

Ja sabem calcular costos: comptar operacions línia a línia, compondre seqüències (sumar) i bucles (multiplicar, o sumar la sèrie si són dependents), distingir millor/pitjor/cas mitjà segons la garantia que necessitem, repartir costos puntuals cars mitjançant l'anàlisi amortitzada (la llista dinàmica com a exemple estrella) i resoldre recurrències de divideix i venceràs amb el teorema mestre. Aplicat a Rutalia, el diagnòstic és clar: el detector de duplicats quadràtic era el procés de les hores, i un intercanvi temps/memòria l'abaixa a segons.

En l'anàlisi de recurrències ha aparegut un protagonista que encara no hem estudiat com es mereix: els algorismes que es criden a si mateixos. A la propera lliçó, Recursió i Programació Dinàmica, aprendrem a dissenyar recursions correctes (cas base, avanç, pila de crides), a fer servir divideix i venceràs com a esquema general i a rescatar les recursions que repeteixen feina mitjançant memoització i programació dinàmica — amb un problema de repartiment de Rutalia sobre la quadrícula de la ciutat com a fil pràctic.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats