Al llarg del curs hem anat deixant afirmacions a compte: que imbricar dos bucles quadruplica la feina en doblar les dades (03-03), que la cerca binària resol en vint comparacions el que a la lineal li costa un milió (06-01), que sorted és 3.600 vegades més ràpid que la nostra bombolla (06-02) i que el Fibonacci ingenu «explota» (06-03). Totes parlen del mateix: quant costa un programa segons la mida de les seves dades. Aquesta lliçó et dona per fi el vocabulari per dir-ho amb precisió.

Aquest vocabulari s'anomena notació Big-O, i és una d'aquelles eines que et canvien la manera de mirar el codi: així que la tens, pots obrir una funció que no has escrit tu i saber, sense executar-la, si aguantarà mil dades o dues-centes mil. També aprendràs el contrari, que importa igual: quan no cal optimitzar res.

1. Per què no es mesura en segons
2. Què es compta al seu lloc
3. La notació Big-O i com se simplifica
4. Catàleg de complexitats
5. La taula del creixement
6. Com analitzar un fragment de codi
7. Tres fragments de TascaFàcil analitzats
8. Pitjor cas, millor cas i cas mitjà
9. Complexitat en espai i l'intercanvi temps-memòria
10. Cost de les operacions habituals en Python
11. Quan optimitzar i quan no
12. TascaFàcil amb 20 tasques i amb 200.000
13. Errors comuns i consells
14. Exercicis
15. Conclusió del mòdul

A 06-02 vam mesurar la bombolla amb time.perf_counter() i van sortir 11 segons per a 10.000 elements. És una dada útil, però no serveix per comunicar res fora d'aquell moment concret, perquè depèn de:

• La màquina: un portàtil de fa vuit anys i un servidor modern difereixen en un factor de deu.
• El llenguatge i la seva versió: la mateixa bombolla en C és unes cinquanta vegades més ràpida que en Python.
• El que estigués fent l'ordinador en aquell instant: un altre programa, l'antivirus, el navegador.
• Les dades concretes que li van tocar: una llista gairebé ordenada o una del revés donen temps diferents.

Si et dic «la meva funció triga 0,4 segons», no saps si és bona. Si et dic «la meva funció dobla el seu temps cada vegada que dobla el nombre de tasques», ja saps tot el que importa: saps que amb 200.000 tasques anirà 10.000 vegades més lenta que amb 20, i això és cert en qualsevol ordinador i en qualsevol llenguatge.

Aquest és el canvi de mentalitat: en comptes de mesurar quant triga, descrivim com creix allò que triga quan creixen les dades. És una propietat de l'algorisme, no de la màquina.

Es compten operacions elementals en funció de la mida de l'entrada, que per conveni s'anomena n. Una operació elemental és aquella el cost de la qual no depèn de la mida de les dades: una suma, una comparació, una assignació, accedir a llista[i], cridar una funció.

Sumant: 1 + n + n + 1, és a dir, 2n + 2 operacions. L'important no és el nombre exacte —depèn de com comptis— sinó la forma de l'expressió: hi ha un terme que creix amb n i uns afegits que no. I el primer que cal entendre és que n no és «quantes dades hi ha» en abstracte, sinó la mida d'allò que fa créixer la feina: aquí, el nombre de tasques de l'agenda.

La notació Big-O (o notació asimptòtica) descriu com creix el nombre d'operacions quan n es fa gran, ignorant tot allò que deixa d'importar a aquella escala. S'escriu O(...) i es llegeix «de l'ordre de».

Formalment és una fita superior: dir que un algorisme és O(n) significa que el seu cost no creix més ràpid que n, tret d'un factor constant. I d'aquí surten les dues regles de simplificació:

• S'ignoren les constants multiplicatives. 3n i n són tots dos O(n): un algorisme tres vegades més lent continua doblant el seu temps en doblar les dades. La constant depèn de la màquina; la forma de créixer, no.
• S'ignoren els termes menors. A n² + 500n + 1000, quan n val un milió, n² és un bilió i 500n són cinc-cents milions: el segon terme és el 0,05 % del total. Queda O(n²).

La conseqüència pràctica d'aquesta màniga ampla és que Big-O no compara dos algorismes amb la mateixa forma: entre dos algorismes O(n), un pot ser cinc vegades més ràpid que l'altre i Big-O no ho dirà. Per a això hi ha time.perf_counter(). Big-O respon una altra pregunta, molt més important: què passarà quan les dades creixin?

Aquestes sis cobreixen pràcticament tot el que et trobaràs, i de totes ja en tens un exemple en aquest curs:

Val la pena aturar-se en dues. O(1) no significa «ràpid», significa «el mateix cost sigui quina sigui la mida»: accedir a llista[999999] costa el mateix que a llista[0], perquè Python calcula l'adreça de memòria en comptes de recórrer. I O(log n) és gairebé tan bo com O(1): el logaritme en base 2 d'un milió és 20, i el de mil milions és 30. Un algorisme logarítmic amb prou feines nota que les dades creixin.

A l'altre extrem, O(2ⁿ) és un mur: cada element nou duplica la feina total. Amb n = 60 no hi ha ordinador al món que acabi, i per això el Fibonacci ingenu era inservible. Ordenats de millor a pitjor:

Els números són més eloqüents que les corbes. Operacions aproximades per a cada mida:

Traduïm l'última fila a temps, suposant deu milions d'operacions per segon, que és un ordre de magnitud raonable per a Python:

Aquí hi ha tota la lliçó en una taula. Amb un milió de dades, un algorisme O(n log n) respon mentre esperes i un O(n²) no acaba mai a la pràctica. I fixa't en una cosa crucial: amb n = 10 tots són instantanis. La complexitat només importa quan les dades creixen, i aquesta observació serà la secció 11.

Tres regles pràctiques basten per al 95 % dels casos:

1. Instruccions soltes (assignacions, comparacions, accessos per índex o per clau): O(1).
2. Els bucles seqüencials se sumen; els bucles imbricats es multipliquen. Dos bucles seguits de n voltes són n + n = 2n → O(n). Un bucle de n voltes dins d'un altre de n voltes són n × n → O(n²).
3. Es pren el terme dominant. Si un fragment fa un sorted (O(n log n)) i després un recorregut (O(n)), el total és O(n log n), perquè mana el major.

El càlcul és 1 + n + n + n² = n² + 2n + 1, que se simplifica a O(n²). I aquesta és la lliçó de disseny més rendible de l'anàlisi: el parell de bucles imbricats domina sobre tota la resta. Optimitzar els dos primers bucles no serviria de res; l'únic canvi que importa és eliminar la imbricació, cosa que saps fer des de 06-01 amb un índex.

Hi ha dos paranys freqüents en analitzar. El primer: una crida a una funció té el cost de la funció, no O(1). Si dins d'un bucle de n voltes crides sorted sobre l'agenda, el total és n × n log n, no n. El segon: l'operador in sobre una llista és O(n), així que un if x in llista dins d'un bucle és un bucle imbricat disfressat.

Fragment 1: resum_per_responsable (des de la v0.10), que compta les tasques de cada persona amb un diccionari.

Un bucle de n voltes amb feina O(1) a dins: O(n). És òptim, perquè per comptar cal mirar totes les tasques almenys una vegada. La clau és que recompte.get(...) sigui O(1); si en comptes d'un diccionari féssim servir una llista de noms i un .index(), cada volta seria O(n) i el total O(n²).

Fragment 2: mostrar_llistat (v0.13), que ordena abans d'imprimir.

sorted és O(n log n) i el recorregut és O(n); el terme dominant mana: O(n log n). No es pot fer millor mentre calgui ordenar, i aquest és l'argument honest per no obsessionar-se: la part cara no és el teu codi, és l'ordenació, i l'ordenació ja la fa Timsort.

Fragment 3: detectar títols duplicats, escrit de la manera ingènua.

Bucles imbricats: O(n²). Amb 20 tasques són unes 190 comparacions, res. Amb 200.000 serien vint mil milions: hores d'espera. La versió amb conjunt, que ja saps escriure des de 05-03, resol el mateix en O(n):

Mateix resultat, un sol bucle. Aquest és l'exemple perfecte de per què la lliçó importa: el segon codi no és més llest, és més barat, i la diferència només es veu si saps comptar.

Un mateix algorisme pot costar coses molt diferents segons les dades concretes que li toquin. Es distingeixen tres escenaris, i ja els vas veure a la cerca lineal de 06-01:

Quan algú diu «aquest algorisme és O(x)» sense precisar, es refereix al pitjor cas. És la convenció, i té una raó sòlida: el pitjor cas és una garantia. Si el pitjor cas és O(n log n), saps que mai no trigarà més, passin les dades que passin. El cas mitjà és una expectativa, no una promesa, i hi ha algorismes famosos —el quicksort de 06-02— amb un cas mitjà excel·lent i un pitjor cas dolent.

El temps no és l'únic que es consumeix: també hi ha complexitat en espai, que mesura quanta memòria extra necessita un algorisme a més de les dades d'entrada.

Les dues últimes files són el famós intercanvi temps-memòria: es gasta memòria per guanyar temps. El cas de la memoïtzació és demolidor: passa Fibonacci de O(2ⁿ) a O(n) en temps, a canvi de O(n) en espai. És dels millors negocis que existeixen en programació.

L'índex invertit és el mateix tracte en petit: index_per_responsable costa O(n) construir-lo i O(n) de memòria, i a canvi cada consulta «què té el Luis?» passa de O(n) a O(1). Amb una consulta no compensa; amb quinze al dia, es paga sol. I hi ha una tercera dimensió que el tracte ignora i convé no oblidar: l'índex s'ha de mantenir actualitzat, i aquest cost és de manteniment del codi, no de temps d'execució.

Aquesta taula és de les coses més útils que t'enduràs del mòdul. Amb n = nombre d'elements:

Les files en negreta són les que causen problemes reals. insert(0, x) i pop(0) són O(n) perquè una llista desa els seus elements consecutius en memòria: ficar o treure pel principi obliga a desplaçar tots els altres. Un bucle que fa pop(0) n vegades és O(n²) sense que ho sembli. La solució de la biblioteca estàndard és collections.deque, una llista doblement enllaçada on tots dos extrems són O(1).

I x in llista és O(n) mentre que x in conjunt és O(1), que és la traducció a aquest vocabulari de tot el que vam veure a 06-01. Canviar una llista per un conjunt és l'optimització més barata i més rendible que existeix: una línia de codi i un canvi de complexitat.

Aquí arriba la part que gairebé mai no s'explica, i és tan important com la resta. La majoria de les optimitzacions no calen.

• Mentre n sigui petit, la claredat mana. Amb 20 tasques, un algorisme O(n²) fa 400 operacions: microsegons. Reescriure aquest codi per fer-lo O(n) el torna més difícil de llegir a canvi d'un estalvi que ningú no percebrà.
• Mesura abans de tocar. La intuïció sobre on és la lentitud és notòriament dolenta. Fes servir time.perf_counter() al voltant dels trossos sospitosos i descobreix el coll d'ampolla en comptes de suposar-lo. A la majoria de programes reals, el temps se'n va en la xarxa o el disc, no en el teu bucle.
• Optimitza la complexitat, no les constants. Si cal millorar alguna cosa, passar de O(n²) a O(n) canviant una llista per un conjunt val mil vegades més que estalviar tres operacions dins d'un bucle.
• Però tria bé des del principi quan és gratis. Escriure if x in conjunt en comptes de if x in llista no costa esforç extra ni llegibilitat. Això no és optimitzar prematurament: és no espatllar el programa per descuit.

La regla que resumeix tot això és de Donald Knuth i té mig segle: l'optimització prematura és l'arrel de tots els mals. Escriu codi clar i correcte; mesura; i optimitza només el que la mesura assenyali. Big-O no hi és perquè ho optimitzis tot, sinó perquè sàpigues què passarà quan les dades creixin i detectis a temps el que no aguantarà.

Analitzem el programa sencer, que va per la v0.14, en els dos escenaris.

Amb 20 tasques, tot està bé i no hi ha res per canviar. Aquest és el veredicte honest, i no una concessió: el programa és clar, correcte i respon a l'instant. Optimitzar-lo seria feina malgastada.

Amb 200.000 tasques, en canvi, l'anàlisi diu exactament què tocar i en quin ordre:

1. Eliminar qualsevol O(n²), començant per la detecció de duplicats: la versió amb conjunt de la secció 7 ho arregla en quatre línies. És l'única cosa veritablement urgent.
2. Construir l'índex una sola vegada en arrencar i mantenir-lo al dia a cada alta i cada baixa, en lloc de reconstruir-lo a cada consulta. Passa les cerques per responsable de O(n) a O(1).
3. No ordenar l'agenda sencera per mostrar vint línies. Si el llistat es pagina, heapq.nsmallest(20, agenda, key=clau_ordre) és O(n log 20) en comptes de O(n log n).
4. Deixar de carregar i desar el fitxer complet. Un JSON de 200.000 tasques es llegeix sencer en memòria cada vegada; a aquesta escala la resposta no és un algorisme millor, és una base de dades, que indexa, cerca i desa només el que canvia.

Fixa't en l'ordre: primer es treuen les complexitats dolentes, després s'apliquen intercanvis temps-memòria i només al final es canvia d'eina. I fixa't en el que no hi apareix: reescriure sorted, microoptimitzar les f-strings o treure funcions per estalviar crides. Això no mouria l'agulla.

Confondre «ràpid» amb «bona complexitat». Un algorisme O(n²) ben escrit pot guanyar-ne un O(n log n) per a n petit, perquè les constants que Big-O ignora existeixen de debò. Timsort, sense anar més lluny, ordena els trams curts amb inserció justament per això.

Oblidar el cost del que es crida. if titol in [t["titol"] for t in agenda] sembla una línia innocent i és O(n) cada vegada: construeix una llista sencera i la recorre. Dins d'un bucle, O(n²).

Creure que O(1) significa instantani i O(n²) significa inacceptable. Són formes de créixer, no velocitats. O(n²) amb n = 20 és perfecte; O(n) amb una operació costosa a dins pot ser un desastre.

Analitzar el millor cas sense dir-ho. «La meva cerca és O(1) perquè normalment és al principi» és una mitja veritat. Per conveni es parla del pitjor cas, que és el que dona garanties.

Optimitzar sense mesurar. Canviar codi «perquè sembla lent» sol empitjorar la llegibilitat sense millorar el temps. Mesura, localitza i llavors actua.

Consell: aprèn a veure els bucles imbricats. No sempre estan indentats l'un dins de l'altre. Un in sobre una llista, un .index(), una comprensió o una crida a una altra funció que recorre són bucles ocults. Pregunta't sempre: aquesta línia recorre alguna cosa?

Consell: el millor canvi sol ser d'estructura de dades, no d'algorisme. Llista → conjunt per a pertinença; llista → diccionari per cercar per clau. Una línia, i la complexitat baixa un esglaó sencer.

Indica la complexitat en temps de cada fragment, en funció de n = len(agenda), i justifica la resposta en una frase.

Aquesta funció comprova quines tasques d'una llista d'encàrrecs nous ja existeixen a l'agenda. Digues la seva complexitat, reescriu-la perquè sigui O(n + m) (sent m el nombre d'encàrrecs nous) i indica quanta memòria extra gasta la nova versió.

Escriu una funció que mesuri amb time.perf_counter() quant triga x in llista davant de x in conjunt cercant un element que no hi és, per a n = 10.000 i n = 100.000. Prediu abans d'executar què li passarà a cada temps en multiplicar n per deu, i comprova si has encertat.

Solució 1.

El (b) és el cas més instructiu: no hi ha dos bucles indentats a la vista, però la comprensió de dins és el bucle interior. La versió correcta construeix el conjunt de títols una sola vegada, fora del bucle, i queda en O(n).

Solució 2.

La versió original és O(n × m): per cada encàrrec recorre l'agenda sencera. La reescriptura canvia el bucle interior per un conjunt:

Construir el conjunt costa O(n) i la comprensió O(m), així que el total és O(n + m). Amb 200.000 tasques i 100 encàrrecs, es passa de 20 milions de comparacions a 200.100 operacions: unes cent vegades menys. El cost és O(n) de memòria extra —el conjunt de títols—, i és l'intercanvi temps-memòria en la seva forma més neta: una línia de més, un esglaó de complexitat menys.

Solució 3.

La predicció és directa a partir de la taula de la secció 10: in sobre una llista és O(n), així que en multiplicar n per deu el temps es multiplica per deu; sobre un conjunt és O(1), així que no canvia. En executar-ho veuràs justament això: la llista passa d'unes dècimes de mil·lisegon a uns quants mil·lisegons, mentre que el conjunt es queda clavat en l'ordre de la milionèsima de segon, mesuri el que mesuri. Cercar l'element absent és deliberat: és el pitjor cas de la llista, que obliga a recórrer-la sencera, i en el conjunt no canvia res. Guarda aquest experiment: és la demostració pràctica de tot el mòdul en vint línies.

L'eficiència no es mesura en segons perquè els segons depenen de la màquina, del llenguatge i de la sort. Es descriu comptant operacions elementals en funció de n i quedant-se amb com creixen: això és la notació Big-O, una fita superior en què s'ignoren les constants multiplicatives i els termes menors, de manera que 3n + 5 és O(n) i n² + 500n és O(n²). El catàleg cap en una línia —O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)— i totes tenen el seu exemple en aquest curs, des de l'accés a un diccionari fins al Fibonacci ingenu. Per analitzar codi basten tres regles: les instruccions soltes són O(1), els bucles seqüencials se sumen i els imbricats es multipliquen, i mana el terme dominant. Per conveni es parla del pitjor cas, perquè és l'únic que ofereix garanties. I al costat del temps hi ha la complexitat en espai, amb el seu intercanvi temps-memòria: memoïtzació i índexs invertits gasten O(n) de memòria per rebaixar el temps un esglaó sencer. La taula de costos de llistes, diccionaris i conjunts —amb in en O(n) davant d'O(1), i els insert(0, x) i pop(0) que són O(n) sense semblar-ho— és la xuleta que faràs servir cada dia. Però la conclusió més important és la contrària: mentre n sigui petit, la claredat mana; mesura abans de tocar i optimitza només el que la mesura assenyali.

Amb això es tanca el mòdul 6, i amb ell les caixes negres que arrossegàvem. Saps cercar: linealment amb sortida primerenca, binàriament descartant meitats sobre dades ordenades i per clau gràcies a la taula hash, a més de preparar índexs invertits quan una consulta es repeteix. Saps ordenar: selecció, inserció i bombolla amb el seu sentinella, la diferència entre estable i inestable, l'estratègia de divisió que hi ha darrere de mergesort i quicksort, i l'ús professional de sorted/.sort() amb key, reverse i tuples per a diversos criteris. Saps fer servir la recursivitat amb el seu cas base i el seu cas recursiu, reconèixer quan guanya —dades amb forma d'arbre, algorismes que divideixen— i arreglar la seva feina repetida amb memoïtzació. I ara saps dir quant costa tot això. TascaFàcil ha arribat a la v0.14: cerca, ordena per dos criteris, reparteix el pla de demà i suma projectes desglossats a qualsevol profunditat.

I tanmateix, mira què sosté tot això: una llista de diccionaris. Res no impedeix que a un diccionari li falti la clau completada, que un altre tingui prioritat escrita com a "Alta", o que un tercer arrossegui un camp inventat que ningú més no entén; el programa no protestarà fins que rebenti per un KeyError a mitja llista. I les funcions que operen sobre tasques —mostrar_fitxa, dies_totals, clau_ordre— són escampades pel fitxer, separades de les dades que manipulen, sense res que digui que formen un conjunt. A De les dades als objectes: classes i instàncies comença el mòdul 7, on dades i comportament deixen d'anar per separat: aprendràs a definir què és exactament una tasca, garantir que totes neixen completes i desar al seu costat les operacions que els pertanyen.