Al Mòdul 1 vam aprendre el llenguatge de l'eficiència: la notació asimptòtica. Ara aprendrem a fer-lo servir: donat un fragment de codi Python real, com se'n calcula la complexitat temporal? En aquesta lliçó desenvoluparem el mètode d'anàlisi línia a línia: assignar un cost a cada operació, sumar els costos de les línies seqüencials, multiplicar per les repeticions dels bucles i simplificar amb les regles que ja coneixem. L'aplicarem pas a pas a les funcions que ja vam escriure per a RutaBus, incloent-hi una funció recursiva, i acabarem amb una cosa que sorprèn molts desenvolupadors: operacions de Python que semblen d'un sol pas però amaguen un bucle a dins.

Dos avisos abans de començar. Primer: les definicions de O, Ω i Θ les vam donar a la lliçó 01-03 i aquí les donem per sabudes (recorda: O gran és una fita superior del creixement del cost). Segon: en tota aquesta lliçó analitzem el pitjor cas — l'escenari d'entrada que més feina provoca —, perquè és l'anàlisi més habitual i la més prudent. A la lliçó 02-03 veurem que també existeixen el millor cas i el cas mitjà, i quan interessa cadascun.

1. El model de cost: operacions elementals
2. Codi seqüencial: sumar costos
3. Bucles simples: multiplicar per les repeticions
4. Anàlisi completa de parada_mes_propera
5. Bucles imbricats: parells de parades connectables
6. Bucles dependents: la suma aritmètica
7. Crides a funcions: el cost no desapareix
8. Funcions recursives: comptar les crides
9. Costos ocults de les operacions de Python

Per analitzar codi sense cronometrar-lo necessitem un acord: què compta com "un pas"? La convenció és aquesta:

• Una operació elemental és qualsevol operació el temps de la qual no depèn de la mida de l'entrada: una assignació (x = 5), una operació aritmètica (a + b, a * b), una comparació (a < b), un accés a una posició de llista (llista[i]), un return.
• Cada operació elemental costa O(1): temps constant. No ens importa si en una màquina concreta una multiplicació triga el doble que una suma — la lliçó 01-03 ja ens va ensenyar que les constants es descarten.

Amb aquest model, analitzar un algorisme es redueix a comptar quantes operacions elementals s'executen en funció de n (la mida de l'entrada). El resultat és una funció de cost T(n) que després simplifiquem al seu ordre asimptòtic.

Compte: la paraula clau és elemental. Com veurem a l'últim apartat, en Python hi ha expressions d'una sola línia que no són elementals perquè amaguen un recorregut complet. De moment, assumim que treballem amb les operacions de la llista anterior.

La primera regla de l'anàlisi línia a línia:

Regla 1 (seqüència): el cost de diverses instruccions executades una rere l'altra és la suma dels seus costos.

Cost total: O(1) + O(1) + O(1) + O(1) = O(1). Tant és que siguin 4 línies o 400: si cap no depèn de n, la suma continua sent una constant i per tant O(1). Aquesta és la traducció pràctica de "descartar constants" que vam veure a 01-03: un bloc seqüencial d'operacions elementals, per llarg que sigui, costa temps constant.

Regla 2 (bucle): el cost d'un bucle és el cost del seu cos multiplicat pel nombre d'iteracions.

Recuperem compta_parades_iteratiu de la lliçó 01-02:

Comptem amb n = nombre de parades:

T(n) = O(1) + O(n) + O(1). Aplicant la regla del terme dominant de 01-03: T(n) = O(n). Lineal: si la xarxa de RutaBus duplica les seves parades, comptar triga el doble.

Un matís important: el nombre d'iteracions no sempre és exactament n. Un bucle for parada in parades[1:] itera n−1 vegades; un que recorre la meitat de la llista itera n/2 vegades. Asimptòticament n−1, n/2 i n són tots O(n) — les constants multiplicatives i additives es descarten. El que importa és que el nombre de voltes creix linealment amb n.

Apliquem el mètode complet a la primera funció que vam escriure per a RutaBus (lliçó 01-01). Anotem el cost de cada línia com a comentari:

Procediment:

1. Abans del bucle: dues línies O(1) → O(1) en total.
2. Cos del bucle: quatre operacions O(1) → O(1) per iteració. (Les dues últimes només s'executen si la comparació és certa, però com que analitzem el pitjor cas assumim que s'executen sempre; i encara que no ho fessin, 2 operacions davant de 4 és una constant que es descarta.)
3. El bucle: O(1) per iteració × (n−1) iteracions = O(n).
4. Després del bucle: O(1).

T(n) = O(1) + O(n) + O(1) = O(n). Confirmem formalment el que a 01-01 només intuíem: trobar la parada més propera amb un recorregut lineal costa temps lineal. Per a la xarxa completa d'una ciutat (milers de parades) continua sent perfectament assumible.

Regla 3 (imbricació): quan un bucle en conté un altre, els costos es multipliquen: iteracions de l'extern × iteracions de l'intern × cost del cos.

Nova necessitat de RutaBus: l'equip de planificació vol saber quins parells de parades són prou a prop per connectar-les amb un tram directe de línia (posem, a menys de 2 km). La solució natural: comparar cada parada amb cadascuna de les altres.

Anàlisi:

• El cos més intern és O(1).
• El bucle intern l'executa n vegades → O(n) per cada volta de l'extern.
• El bucle extern fa n voltes → n × O(n) = O(n²).

La comparació p1["nom"] < p2["nom"] és un truc per processar cada parell una sola vegada (evita examinar tant ("A","B") com ("B","A") i els parells d'una parada amb si mateixa), però no canvia l'ordre: l'if s'avalua en les n² combinacions encara que només prosperi en la meitat, i n²/2 continua sent O(n²).

És greu, un O(n²)? Depèn de n, i aquí connecta amb la taula de temps de 01-03: amb 100 parades són 10.000 comparacions (instantani); amb 10.000 parades d'una àrea metropolitana són 100 milions (segons). Els algorismes quadràtics són el primer senyal d'alarma que un desenvolupador aprèn a detectar: un bucle dins d'un altre bucle, tots dos sobre la mateixa col·lecció.

A parells_connectables hi ha un malbaratament evident: quan p1 és la parada 7, no cal comparar-la amb les parades 0 a 7 (ja s'han comparat abans o és ella mateixa). La versió afinada fa que el bucle intern depengui de l'extern:

Ara el bucle intern no fa sempre n voltes: en fa n−1 quan i=0, n−2 quan i=1... i 0 quan i=n−1. Ja no podem multiplicar sense més; cal sumar les iteracions reals:

Aquesta és la famosa suma aritmètica, i el seu valor exacte és:

Un truc visual per recordar-la: escriu la suma dues vegades, una del dret i una del revés, i aparella termes:

El doble de la suma és n(n−1), per tant la suma és n(n−1)/2. Aplicant les regles de simplificació de 01-03 (descartar constants com el ½, quedar-se amb el terme dominant n²): O(n²).

Conclusió que convé interioritzar: la versió v2 fa la meitat de feina real que la v1 — una millora útil a la pràctica —, però el seu ordre de creixement és el mateix, O(n²). La notació asimptòtica és deliberadament cega als factors constants; per passar d'O(n²) a alguna cosa millor no n'hi ha prou amb retallar iteracions: cal canviar d'estratègia (d'això tracta el Mòdul 3). Aquest patró "bucle intern que comença on va l'extern → n(n−1)/2 → O(n²)" apareix constantment: memoritza'l.

Regla 4 (crides): el cost d'una crida a funció és el cost d'executar-ne el cos amb els arguments donats. Encapsular codi en una funció no el fa gratuït.

A parada_mes_propera vam dir alegrement que distancia(...) era O(1). Això cal justificar-ho mirant-ne el cos:

Restes, quadrats, una arrel: un nombre fix d'operacions elementals, independent de quantes parades tingui la xarxa → O(1). Correcte.

Però compte amb aquest altre cas, molt típic:

Una sola línia, dues crides... i cada crida a hi_ha_parada_iterativa (lliçó 01-02) és un recorregut lineal: O(n). Total: O(n) + O(n) = O(n), no O(1). I si aquesta funció es crida dins d'un bucle sobre les n parades, el conjunt passa a ser O(n²). La regla pràctica: quan vegis una crida, pregunta't sempre quant costa per dins — o busca-ho a la seva documentació. Aquest serà exactament el problema dels "costos ocults" de l'últim apartat.

Per a una funció recursiva no hi ha cap bucle per multiplicar, però la idea és la mateixa amb una altra disfressa:

Cost d'una recursió = (nombre de crides) × (cost de cada crida, sense comptar la crida recursiva)

Analitzem compta_parades_recursiu de la lliçó 01-02:

Pas 1 — comptar les crides. Cada crida treballa amb una llista una unitat més curta que l'anterior. Per a una línia amb 4 parades:

Per a n parades: n + 1 crides. El nombre de crides creix linealment amb n.

Pas 2 — cost de cada crida. Aquí ve la sorpresa. La comparació i el + 1 són O(1), però parades[1:] crea una llista nova copiant tots els elements menys el primer: si la llista té k elements, l'slice costa O(k) (ho confirmarem a la taula de l'apartat següent). Així doncs, les crides costen, respectivament, n, n−1, n−2, ..., 1, 0 operacions de còpia. Et sona, aquesta suma? És una altra vegada la suma aritmètica: n(n+1)/2 → O(n²).

Resultat honest: tal com està escrita en Python, compta_parades_recursiu és O(n²), mentre que la seva germana iterativa és O(n). Si la reescrivíssim passant un índex en lloc de trossejar la llista (evitant l'slice), cada crida seria O(1) i la recursió completa quedaria en O(n), com dicta la intuïció de "n+1 crides de cost constant". Doble moral: (1) la tècnica per a recursions és comptar crides i multiplicar pel cost de cadascuna; (2) en Python, aquest cost "de cadascuna" pot amagar còpies.

Per a recursions més riques — per exemple una funció que es crida dues vegades a si mateixa amb la meitat del problema, com farà merge sort — aquest recompte artesanal es formalitza amb les anomenades equacions de recurrència. Encara no les necessitem: les plantejarem i les resoldrem per a un cas real a la lliçó 04-03 (Merge Sort). Queda't amb la versió intuïtiva: dibuixa l'arbre de crides, compta quantes n'hi ha i quant costa cadascuna.

Python és un llenguatge de molt alt nivell: una sola expressió pot executar un bucle complet en C per sota. Per a l'anàlisi de complexitat això és una trampa: el codi es llegeix com una línia però costa com un bucle. Aquesta taula recull els casos que més anàlisis arruïnen (n = mida de la col·lecció implicada; tots en el pitjor cas):

Vegem dues d'aquestes trampes en codi de RutaBus.

Trampa 1: in sobre llista dins d'un bucle. Volem les parades comunes a dues línies (possibles transbordaments):

Sembla un bucle simple → O(n), però l'in sobre una llista és un recorregut lineal amagat: n iteracions × O(n) per comprovació = O(n²). És exactament la mateixa imbricació de parells_connectables, només que un dels dos bucles no es veu. Solució idiomàtica: convertir linia_b en un set (parades_b = set(linia_b), cost O(n) una sola vegada) i preguntar parada in parades_b, que és O(1) — l'algorisme complet baixa a O(n). El preu és memòria extra, i mesurar aquest preu és justament el tema de la propera lliçó.

Trampa 2: concatenació de strings en bucle. Generar el rètol amb el recorregut d'una línia:

A la volta k, retol ja fa proporcionalment k caràcters i la concatenació el copia sencer: costos 1, 2, 3, ..., n → suma aritmètica → O(n²). La versió idiomàtica, " - ".join(parades), construeix el resultat en un sol pas de cost O(total de caràcters): lineal.

• Sumar on cal multiplicar (i viceversa): les instruccions en seqüència se sumen; les instruccions dins d'un bucle es multipliquen per les iteracions. Dos bucles seguits sobre n elements són O(n) + O(n) = O(n); un bucle dins d'un altre és O(n · n) = O(n²).
• Creure que menys línies = menys cost: if parada in linia_b és una línia i costa O(n). El cost es mesura en operacions executades, no en línies escrites. Davant de qualsevol funció o mètode de biblioteca, consulta'n el cost (la taula anterior cobreix l'essencial).
• Concloure O(n²/2) o O(3n): són ordres mal escrits. Després de comptar, simplifica sempre amb les dues regles de 01-03: fora constants, fora termes no dominants. O(n²/2) és O(n²); O(3n) és O(n).
• Oblidar de què és n: a transbordaments hi ha dues entrades (dues línies). Si tenen mides diferents, el rigorós és dir O(a · b). Diem O(n²) assumint mides semblants, però convé ser explícit quan no ho són.
• Ignorar el cost dels slices en recursions: f(llista[1:]) sembla elegant però copia la llista a cada nivell. Si la recursió té profunditat n, aquestes còpies sumen O(n²). Alternativa: passar índexs (f(llista, i+1)).
• Consell: entrena l'ull amb aquesta drecera mental — quantes vegades s'executa la línia més interna del codi? Aquest recompte, simplificat, és gairebé sempre la complexitat de l'algorisme.

Exercici 1. Analitza línia a línia la funció següent de RutaBus i dona'n la complexitat temporal en el pitjor cas. Indica quantes vegades s'executa cada línia.

Exercici 2. L'equip de qualitat de RutaBus va escriure aquesta funció per detectar parades duplicades al fitxer mestre de la xarxa. Analitza'n la complexitat i proposa'n una versió O(n) fent servir la taula de costos de Python. Justifica el cost de totes dues.

Exercici 3. Sense executar-la, determina la complexitat d'aquesta funció recursiva que inverteix l'ordre de les parades d'una línia (útil per mostrar el trajecte de tornada). Pista: compta les crides i fixa't en el cost de cada crida.

Solució 1. Les dues assignacions inicials i el return són O(1) (s'executen 1 vegada). Cada bucle executa el seu cos n vegades amb cost O(1) per iteració → O(n) cadascun. Són bucles en seqüència, no imbricats, així que se sumen: T(n) = O(1) + O(n) + O(n) + O(1) = O(2n) → O(n). Error comú aquí: veure dos for i respondre O(n²) — només es multiplica quan l'un és dins de l'altre.

Solució 2. És el patró de bucle dependent: el bucle intern fa n−1, n−2, ..., 1, 0 voltes → suma aritmètica n(n−1)/2 → O(n²) en el pitjor cas (sense duplicats: cal comprovar tots els parells; fixa't que si troba un duplicat aviat acaba abans — aquesta diferència entre escenaris és justament el tema de 02-03). Versió lineal amb un conjunt:

n iteracions × O(1) = O(n). El preu: fins a O(n) de memòria extra per a vistes — ho quantificarem a la lliçó 02-02.

Solució 3. Crides: igual que compta_parades_recursiu, una per mida n, n−1, ..., 0 → n+1 crides. Cost de cada crida de mida k: l'slice parades[1:] costa O(k) i a més la concatenació llista + [x] crea una llista nova copiant els k−1 elements ja invertits: un altre O(k). Total per crida: O(k). Sumant k = n, n−1, ..., 1: suma aritmètica → O(n²). La inversió iterativa (recórrer de darrere cap endavant amb append, o directament parades[::-1], que copia una sola vegada) és O(n).

Ja sabem calcular, i no només anomenar, la complexitat temporal d'un algorisme. El mètode cap en quatre regles: les operacions elementals costen O(1); el codi en seqüència suma; els bucles multipliquen per les seves iteracions (i quan el bucle intern depèn de l'extern, apareix la suma aritmètica n(n−1)/2 → O(n²)); i les crides a funcions costen el que costa el seu cos — també les recursives, on comptem crides i multipliquem pel cost de cadascuna. Amb aquest mètode hem confirmat que parada_mes_propera és O(n), hem vist néixer l'O(n²) als parells de parades connectables i hem destapat els costos ocults de Python: l'in sobre llistes, els slices i la concatenació de strings, capaços de convertir un aparent O(n) en un O(n²) real. Tot això, recorda, mesurant el pitjor cas.

Però el temps és només la meitat de la factura. En substituir una llista per un set per accelerar transbordaments, o en veure que cada crida recursiva apila una còpia de la llista, hem estat pagant amb memòria sense comptabilitzar-ho. A la propera lliçó (02-02) aprendrem a fer exactament la mateixa anàlisi línia a línia, però mesurant bytes en lloc de passos: la complexitat espacial.