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

Complexitat algorísmica i notació Big O

Següent ►
►

A la lliçó 01-02 vas comprovar amb el cronòmetre que cercar una tasca en una llista d'un milió d'elements triga moltíssim més que cercar-la en un índex. Però els cronòmetres tenen un problema: les seves xifres depenen del teu ordinador, de la teva versió de Python i fins i tot de què més estigui executant la teva màquina en aquell moment. Necessitem una manera de parlar d'eficiència que sigui independent de tot això, i aquesta manera és la notació Big O. És, sense exagerar, el vocabulari més important del curs: a partir d'aquí, cada operació de cada estructura vindrà etiquetada amb el seu Big O. Dedica a aquesta lliçó el temps que calgui.

Contingut

  1. Complexitat temporal i espacial: comptar en lloc de cronometrar
  2. La notació Big O: què significa exactament
  3. Les classes habituals, amb exemples en Python
  4. Comparativa: quant importa la classe de complexitat
  5. Millor cas, pitjor cas i cas mitjà
  6. Cost amortitzat (menció breu)
  7. Mesurant TaskFlow amb timeit: la teoria contra el cronòmetre

Complexitat temporal i espacial: comptar en lloc de cronometrar

La idea central de la complexitat algorísmica és deixar de mesurar segons i començar a comptar operacions. En lloc de preguntar "quant triga?", preguntem: quants passos executa l'algorisme en funció de la mida de l'entrada, n?

  • Complexitat temporal: quantes operacions elementals (comparacions, sumes, assignacions...) fa l'algorisme a mesura que creix n.
  • Complexitat espacial: quanta memòria addicional necessita a mesura que creix n (sense comptar l'entrada mateixa).

Comptem passos a la cerca seqüencial de TaskFlow:

def cercar_en_llista(tasques, id_cercat):
    for tasca in tasques:             # es repeteix fins a n vegades
        if tasca["id"] == id_cercat:  # 1 comparacio per volta
            return tasca
    return None

Si hi ha n tasques i la cercada és al final (o no hi és), el bucle fa n voltes amb una comparació cadascuna: unes n operacions. Si dupliquem les tasques, dupliquem la feina. Diem que el temps creix linealment amb n. La seva complexitat espacial, en canvi, és constant: tingui la llista la mida que tingui, la funció només necessita un grapat de variables auxiliars.

Aquesta anàlisi té dues virtuts que el cronòmetre no té:

  1. És universal: n operacions són n operacions al teu portàtil i en un servidor de producció.
  2. Prediu el futur: sabem què passarà amb 10 milions de tasques sense necessitat de provar-ho.

La notació Big O: què significa exactament

En comptar operacions sorgeixen detalls molestos: la cerca fa exactament n comparacions, o n comparacions més n accessos al camp "id" més 1 retorn, és a dir, 2n + 1 operacions? La resposta de la notació Big O és: tant és. L'únic que importa és com creix el cost quan n es fa gran.

Big O descriu l'ordre de creixement del cost d'un algorisme quan n tendeix a valors grans, ignorant constants multiplicatives i termes menors.

Les dues regles de simplificació:

  1. Ignora les constants: 2n + 1 operacions → O(n). Tant fa 2n que 5n: tots dos es dupliquen en duplicar n, i això és el que Big O captura.
  2. Queda't amb el terme dominant: n² + 3n + 20 → O(n²). Quan n = 1.000.000, el terme n² aporta un bilió d'operacions i el 3n amb prou feines tres milions: els termes menors es tornen irrellevants.
def exemple(tasques):
    n = len(tasques)               # 1 operacio
    print(tasques[0])              # 1 operacio
    for t in tasques:              # n operacions
        print(t["titol"])
    for t1 in tasques:             # n * n = n² operacions
        for t2 in tasques:
            if t1["id"] == t2["id"] and t1 is not t2:
                print("id duplicat!")

Cost total: 2 + n + n². Aplicant les dues regles: O(n²). El bloc que domina és el doble bucle; per a n gran, els altres ni es noten.

Un apunt de rigor: formalment, Big O expressa una cota superior del creixement ("no creix més ràpid que..."). En l'ús quotidià de la professió —i en aquest curs— s'empra com a sinònim de "el seu cost creix com...", que és la interpretació pràctica que necessites.

Les classes habituals, amb exemples en Python

Gairebé tot el que analitzarem al curs cau en cinc classes. Cadascuna, amb un exemple real sobre les tasques de TaskFlow:

O(1) — constant

El cost no depèn de n. Tant fa que hi hagi 10 tasques o 10 milions.

def primera_tasca(tasques):
    return tasques[0]         # accedir per index no recorre res

def total_tasques(tasques):
    return len(tasques)       # Python desa la mida ja calculada

Accedir a tasques[0], a tasques[500_000] o preguntar len(tasques) costa el mateix: un pas. Per què l'accés per índex és O(1) ho entendràs a fons a la lliçó 01-05.

O(log n) — logarítmica

El cost creix amb el logaritme de n: cada pas descarta la meitat de les dades. Duplicar n només afegeix un pas més.

def cerca_binaria(tasques_ordenades_per_id, id_cercat):
    """Requereix que les tasques estiguin ordenades per id."""
    inici, fi = 0, len(tasques_ordenades_per_id) - 1
    while inici <= fi:
        mig = (inici + fi) // 2                # mirem el centre
        id_mig = tasques_ordenades_per_id[mig]["id"]
        if id_mig == id_cercat:
            return tasques_ordenades_per_id[mig]
        elif id_mig < id_cercat:
            inici = mig + 1                    # descartem la meitat esquerra
        else:
            fi = mig - 1                       # descartem la meitat dreta
    return None

Com funciona: com que les tasques estan ordenades per id, mirar la del centre ens diu a quina meitat és la cercada, i l'altra meitat es descarta sencera sense mirar-la. Amb un milió d'elements: 1.000.000 → 500.000 → 250.000 → ... → 1 en uns 20 passos. És el mateix truc que fas servir en buscar una paraula en un diccionari de paper: obres pel mig i descartes mitja obra d'un cop d'ull.

O(n) — lineal

El cost creix en proporció directa a n: tocar cada element una vegada.

def comptar_pendents(tasques):
    comptador = 0
    for tasca in tasques:                 # n voltes exactes
        if tasca["estat"] == "pendent":
            comptador += 1
    return comptador

La nostra vella coneguda cercar_en_llista també és O(n). Qualsevol algorisme que necessiti mirar totes les dades almenys una vegada és com a mínim O(n): no hi ha manera de comptar les pendents sense visitar cada tasca.

O(n log n) — gairebé lineal

La classe dels bons algorismes d'ordenació. Intuïció: fer una feina O(log n) per cadascun dels n elements, o dividir el problema per la meitat repetidament ordenant a cada nivell.

tasques_ordenades = sorted(tasques, key=lambda t: t["prioritat"])

El sorted de Python (algorisme Timsort) és O(n log n). No l'implementarem aquí; queda't amb la idea que ordenar bé costa O(n log n), sensiblement més que recórrer (O(n)) però moltíssim menys que comparar-ho tot amb tot (O(n²)).

O(n²) — quadràtica

El cost creix amb el quadrat de n: típicament, un bucle dins d'un altre, tots dos sobre les dades. Duplicar n quadruplica la feina.

def hi_ha_titols_duplicats(tasques):
    for i in range(len(tasques)):             # n voltes
        for j in range(i + 1, len(tasques)):  # fins a n voltes per cada i
            if tasques[i]["titol"] == tasques[j]["titol"]:
                return True
    return False

Cada tasca es compara amb totes les següents: al voltant de n²/2 comparacions, que per la regla de les constants és O(n²). Amb 1.000 tasques, mig milió de comparacions; amb un milió de tasques, cinc-cents mil milions. Les solucions quadràtiques són acceptables només amb dades petites; detectar-les (i saber substituir-les: aquest mateix problema és O(n) amb un set) és una habilitat d'entrevista clàssica.

Existeixen classes pitjors —O(2ⁿ), O(n!)— pròpies de problemes de força bruta; amb prou feines ens les creuarem, però convé saber que existeixen i que són intractables fins i tot amb n modestos.

Comparativa: quant importa la classe de complexitat

Números concrets: passos aproximats que executa cada classe a mesura que creix n (suposant, per traduir a temps, uns 10 milions d'operacions simples per segon en Python):

n O(1) O(log n) O(n) O(n log n) O(n²)
10 1 3 10 33 100
1.000 1 10 1.000 10.000 1.000.000
1.000.000 1 20 10⁶ (~0,1 s) 2·10⁷ (~2 s) 10¹² (~28 hores)

Observa l'última fila: amb un milió d'elements, la diferència entre O(n) i O(n²) és la diferència entre una dècima de segon i més d'un dia. I O(log n) continua sent, a efectes pràctics, instantani. Aquesta taula explica per què l'experiment de la lliçó 01-02 va donar els resultats que va donar, i per què la tria d'estructura importa tant: cada estructura ofereix les seves operacions amb classes de complexitat diferents.

graph TB
    subgraph "Creixement del cost en augmentar n"
        A["O(1): pla"] --- B["O(log n): gairebé pla"]
        B --- C["O(n): recta"]
        C --- D["O(n log n): recta que s'empina"]
        D --- E["O(n²): paràbola — es dispara"]
    end

I la taula que farem servir com a referència durant tot el curs — el cost de les operacions habituals sobre les estructures natives de Python:

Operació list dict / set
Accés per índex llista[i] O(1) —
Accés/inserció per clau — O(1) de mitjana
Cercar si conté (in) O(n) O(1) de mitjana
Afegir al final (append/add) O(1) amortitzat O(1) de mitjana
Inserir/esborrar al principi o al mig O(n) —

Els cognoms "de mitjana" i "amortitzat" s'expliquen als dos apartats següents.

Millor cas, pitjor cas i cas mitjà

Un mateix algorisme pot costar diferent segons la sort de les dades. La cerca seqüencial a TaskFlow:

  • Millor cas: la tasca cercada és la primera → 1 comparació → O(1).
  • Pitjor cas: és l'última o no existeix → n comparacions → O(n).
  • Cas mitjà: si qualsevol posició és igual de probable, unes n/2 comparacions → O(n) (recorda: les constants com ½ s'ignoren).
Escenari Què descriu Quan usar-lo
Millor cas El resultat amb les dades més favorables Gairebé mai: és informació poc fiable
Pitjor cas La garantia màxima: mai no anirà pitjor L'estàndard professional per defecte
Cas mitjà El comportament esperat amb dades típiques Quan el pitjor cas és rar i es coneix la distribució

Llevat que es digui el contrari, quan algú dona un Big O a seques es refereix al pitjor cas: és la garantia que permet dimensionar sistemes ("mai no trigarà més que..."). El cas mitjà importa quan el pitjor cas és extraordinàriament improbable: l'exemple estrella és el dict de Python, la cerca del qual és O(1) de mitjana però pot degradar-se en situacions patològiques raríssimes (ho entendràs en estudiar les col·lisions al mòdul 5). Per això la taula anterior diu "O(1) de mitjana".

Cost amortitzat (menció breu)

Queda un cognom per explicar: l'append de list és "O(1) amortitzat". El cost amortitzat és el cost fet mitjana sobre una seqüència llarga d'operacions: gairebé tots els append són instantanis, però de tant en tant n'hi ha un que costa O(n) perquè la llista s'ha de reorganitzar per dins; repartit aquest cost ocasional entre totes les operacions, surt a O(1) per operació.

De moment, queda't només amb la idea de "car molt de tant en tant, barat gairebé sempre, i de mitjana constant". El perquè exacte —quina reorganització és aquesta i per què surt a compte— és precisament un dels plats forts de la propera lliçó (01-05), quan veurem els arrays dinàmics.

Mesurant TaskFlow amb timeit: la teoria contra el cronòmetre

Tanquem el cercle: la teoria prediu, i timeit verifica. Si cercar_en_llista és O(n), en multiplicar per 10 el nombre de tasques el temps s'hauria de multiplicar per ~10. Comprovem-ho:

import timeit

def crear_tasques(n):
    return [{"id": i, "titol": f"Tasca {i}"} for i in range(n)]

def cercar_en_llista(tasques, id_cercat):
    for tasca in tasques:
        if tasca["id"] == id_cercat:
            return tasca
    return None

for n in (10_000, 100_000, 1_000_000):
    tasques = crear_tasques(n)
    index = {t["id"]: t for t in tasques}
    pitjor = n - 1   # pitjor cas: l'ultima tasca

    t_llista = timeit.timeit(lambda: cercar_en_llista(tasques, pitjor), number=20)
    t_dict = timeit.timeit(lambda: index.get(pitjor), number=20)

    print(f"n={n:>9} | llista: {t_llista:8.4f} s | dict: {t_dict:.6f} s")

Sortida típica (les teves xifres variaran; les proporcions no):

n=   10.000 | llista:   0,0059 s | dict: 0,000002 s
n=  100.000 | llista:   0,0601 s | dict: 0,000002 s
n=1.000.000 | llista:   0,6088 s | dict: 0,000002 s

Lectura de l'experiment:

  • La columna de la llista es multiplica per ~10 a cada fila, exactament el que prediu O(n): cost proporcional a n.
  • La columna del dict no es mou: O(1) en estat pur, confirmant la teoria del cas mitjà.
  • Això és el que Big O et dona i el cronòmetre només t'insinua: a la lliçó 01-02 vam veure que passava; ara sabem quant i per què, i podem predir-ho per a qualsevol n sense executar res.

A partir d'ara, aquest serà el nostre mètode amb cada estructura: analitzar el Big O de les seves operacions sobre el paper i, quan aporti, confirmar-lo amb timeit.

Errors Comuns i Consells

  • Creure que O(1) significa "ràpid" i O(n) "lent". O(1) significa "cost que no depèn de n", no "instantani": una operació O(1) pot ser lenta en termes absoluts, i una O(n) amb n = 20 és menyspreable. Big O parla de creixement, no de velocitat absoluta.
  • Oblidar els costos ocults de Python. element in llista sembla una operació, però és O(n) per dins; llista.insert(0, x) també. Un in sobre llista dins d'un bucle O(n) fabrica un O(n²) invisible: és l'error de rendiment més comú en Python (ho vas veure a l'exercici 2 de la lliçó 01-02).
  • Comparar algorismes pel millor cas. "La meva cerca de vegades encerta a la primera" no diu res d'útil. Analitza el pitjor cas per defecte i esmenta el cas mitjà només quan el sàpigues justificar.
  • Ignorar la complexitat espacial. Crear un índex dict per cercar en O(1) gasta O(n) de memòria addicional. Gairebé sempre compensa, però has de saber que estàs pagant aquest preu: temps i espai s'intercanvien constantment.
  • Consell: quan dubtis del Big O d'un codi, compta els bucles imbricats que depenen de n com a primera aproximació (1 bucle → O(n), 2 d'imbricats → O(n²)) i vigila les operacions amb cost ocult a dins.

Exercicis

Exercici 1: classificar fragments

Indica la complexitat temporal (Big O, pitjor cas) de cada fragment i justifica-ho en una frase:

# (a)
def ultima_tasca(tasques):
    return tasques[-1]

# (b)
def titols_en_majuscules(tasques):
    return [t["titol"].upper() for t in tasques]

# (c)
def parells_de_tasques_conflictives(tasques):
    parells = []
    for a in tasques:
        for b in tasques:
            if a["id"] != b["id"] and a["titol"] == b["titol"]:
                parells.append((a["id"], b["id"]))
    return parells

# (d)
def existeix_id(tasques, id_cercat):
    return any(t["id"] == id_cercat for t in tasques)

Exercici 2: millor, pitjor i mitjà

Per a la funció existeix_id de l'exercici anterior, descriu el seu millor cas, el seu pitjor cas i el seu cas mitjà (suposant que l'id cercat, quan existeix, és en una posició aleatòria uniforme). Dona el Big O de cadascun.

Exercici 3: predicció i verificació empírica

hi_ha_titols_duplicats (vista a l'apartat d'O(n²)) compara cada tasca amb les següents. (a) Prediu: si amb n = 1.000 triga t segons, quant trigarà aproximadament amb n = 2.000 i amb n = 4.000? (b) Verifica-ho amb timeit usant tasques amb títols tots diferents (pitjor cas: no troba res i ho compara tot). (c) Reescriu la funció amb un set perquè sigui O(n) i repeteix la mesura.

Solucions

Solució 1:

  • (a) O(1): l'accés per índex (encara que sigui l'últim, [-1]) no recorre res.
  • (b) O(n): la comprensió visita cada tasca exactament una vegada. (Nota: també gasta O(n) d'espai, perquè crea una llista nova.)
  • (c) O(n²): dos bucles imbricats complets sobre les n tasques → n² comparacions.
  • (d) O(n): any amb un generador va comprovant tasca a tasca i s'atura en trobar la primera coincidència, però en el pitjor cas (no existeix) les recorre totes.

Solució 2:

  • Millor cas: l'id cercat és a la primera posició → 1 comparació → O(1).
  • Pitjor cas: l'id no existeix (o és l'últim) → n comparacions → O(n).
  • Cas mitjà: posició uniforme → n/2 comparacions esperades → O(n) (la constant ½ es descarta). Conclusió típica: millor cas O(1), però l'algorisme "és" O(n), perquè per defecte parlem del pitjor cas.

Solució 3:

(a) O(n²) implica que duplicar n quadruplica el temps: amb n = 2.000 trigarà ~4t; amb n = 4.000, ~16t.

(b) i (c):

import timeit

def hi_ha_titols_duplicats_v2(tasques):
    vistos = set()
    for t in tasques:                   # n voltes
        if t["titol"] in vistos:        # O(1) de mitjana sobre un set
            return True
        vistos.add(t["titol"])          # O(1) de mitjana
    return False                        # total: O(n)

for n in (1_000, 2_000, 4_000):
    tasques = [{"id": i, "titol": f"Tasca {i}"} for i in range(n)]
    t_v1 = timeit.timeit(lambda: hi_ha_titols_duplicats(tasques), number=3)
    t_v2 = timeit.timeit(lambda: hi_ha_titols_duplicats_v2(tasques), number=3)
    print(f"n={n}: O(n²) {t_v1:.3f} s | O(n) {t_v2:.5f} s")

Resultat típic: la versió quadràtica segueix la progressió ×4 predita (per exemple 0,1 s → 0,4 s → 1,6 s), mentre que la versió amb set es limita a duplicar-se (progressió ×2, lineal) i és centenars de vegades més ràpida ja amb n = 4.000. La predicció teòrica i la mesura coincideixen: això és exactament el que Big O promet. (Cost de l'intercanvi: la v2 usa O(n) de memòria extra per al conjunt vistos.)

Conclusió

Ja domines el vocabulari central del curs: la complexitat temporal i espacial compten operacions i memòria en funció de n; la notació Big O captura l'ordre de creixement ignorant constants i termes menors; les classes O(1), O(log n), O(n), O(n log n) i O(n²) cobreixen gairebé tot el que analitzarem, amb diferències que van d'"instantani" a "més d'un dia" amb dades grans; l'anàlisi per defecte és el pitjor cas, reservant el cas mitjà i el cost amortitzat per a quan estan justificats; i timeit permet confirmar empíricament el que la teoria prediu.

Ens queda un deute pendent d'aquesta lliçó: per què l'accés llista[i] és O(1)? I quina reorganització misteriosa fa que append sigui només O(1) amortitzat? Les respostes són un nivell més avall, en com s'organitzen les dades físicament a la memòria. Aquest és el tema de la propera lliçó: arrays i memòria, la base sobre la qual es construeix tota la resta.

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