Comença l'entrenament. En aquesta lliçó no hi ha teoria nova: hi ha una bateria d'exercicis que exercita tot el Mòdul 2 —anàlisi temporal (02-01), anàlisi espacial (02-02) i casos millor/pitjor/mitjà (02-03)— fent servir la notació asimptòtica del Mòdul 1 (01-03). Tots els exercicis treballen sobre codi de RutaBus, la nostra aplicació de mobilitat urbana.

Com treballar aquesta lliçó: intenta cada exercici en paper abans de mirar la solució. De debò. Llegir una solució d'anàlisi de complexitat produeix la sensació de "això ja ho sé"; derivar-la tu mateix és el que construeix el reflex. Si t'encalles més de deu minuts, llegeix la pista (si n'hi ha) i torna-ho a intentar abans de rendir-te.

1. Derivar Θ de bucles simples, imbricats i dependents.
2. Els costos ocults de Python: in sobre llista i insert(0).
3. Complexitat espacial: auxiliar davant de total, i recursió amb slices davant d'índexs.
4. Millor, pitjor i cas mitjà d'una funció de validació.
5. Aparellar cada codi amb el seu ordre de creixement a partir de mesures.
6. Detecta el cost ocult: la funció que sembla lineal però no ho és.

Dificultat: bàsica

RutaBus registra cada fitxatge com una tupla (hora, parada, linia). Analitza aquestes tres funcions i deriva la complexitat temporal Θ de cadascuna en funció de n (la mida de la llista d'entrada). Per a la tercera, calcula a més el nombre exacte d'iteracions del bucle intern.

compta_fitxatges_linia: un sol bucle que recorre els n fitxatges fent feina O(1) a cada volta (una comparació i, de vegades, una suma). Com vam veure a 02-01, el cost és proporcional al nombre d'iteracions: Θ(n). Fixa't que l'if no canvia l'ordre: s'executi o no el cos, la comparació es fa sempre.

matriu_coincidencies: dos bucles imbricats independents (el rang de j no depèn d'i): n · n iteracions amb feina O(1) cadascuna. La creació prèvia de la matriu també costa Θ(n²), però no canvia el total: Θ(n²).

parells_conflictius: aquí el bucle intern depèn d'i. Comptem les iteracions exactes: per a i = 0 n'hi ha n−1, per a i = 1 n'hi ha n−2, …, per a i = n−1 n'hi ha 0. La suma és:

(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2

Com vam veure a 02-01, n(n−1)/2 = n²/2 − n/2, i en simplificar (01-03) descartem constants i termes menors: Θ(n²). El bucle dependent fa la meitat de feina que l'independent, però la meitat d'un quadràtic continua sent quadràtic.

Errors típics: (1) pensar que el bucle dependent és "alguna cosa intermèdia" tipus O(n log n) — no: la sèrie aritmètica dona quadràtic; (2) sumar Θ(n²) + Θ(n²) de la creació de la matriu i dir Θ(2n²) — les constants es descarten.

Dificultat: mitjana

L'equip de dades de RutaBus va escriure aquestes dues funcions. Deriva'n el cost temporal real. Anomena n el nombre de fitxatges/avisos, m la mida de parades_conegudes i k el nombre de parades noves trobades.

Preguntes: (a) quin és el cost de cada comprovació marcada?; (b) quin és el cost total de cada funció?; (c) què passa amb parades_noves en el pitjor cas en què totes les parades són noves?

Pista: repassa la taula de costos ocults de 02-01: x in llista no costa el mateix que x in conjunt, i les llistes de Python estan optimitzades per tocar-ne el final, no el començament.

(a) Com vam veure a 02-01, parada not in parades_conegudes sobre una llista és una cerca lineal: O(m). La segona comprovació, parada not in noves, costa O(k) on k és la mida actual de noves. I resultat.insert(0, avis) desplaça tots els elements existents una posició: O(longitud actual).

(b) parades_noves fa n iteracions i a cadascuna paga O(m) + O(k): total O(n·(m + k)). darrers_primer paga 0 + 1 + 2 + … + (n−1) = n(n−1)/2 desplaçaments: Θ(n²) — la mateixa sèrie aritmètica de l'Exercici 1, aquest cop amagada dins d'un mètode.

(c) Si totes les parades són noves, k creix fins a n i el cost es converteix en O(n·m + n²): la funció que "semblava" un filtratge lineal és quadràtica.

Perquè en quedi constància (la reparació es practica a 06-03, aquí només diagnostiquem): la comprovació seria O(1) amb un set, i darrers_primer seria Θ(n) amb append + reverse() (o directament avisos[::-1]).

Error típic: comptar cada línia de Python com "una operació". La línia if parada not in parades_conegudes: és una línia, però són m comparacions. L'anàlisi línia a línia de 02-01 exigeix conèixer el cost real de cada operació, no la seva longitud tipogràfica.

Dificultat: mitjana

Dues versions recursives de la suma d'ocupació d'un trajecte (llista de passatgers per tram):

Preguntes: (a) espai auxiliar de cada versió; (b) espai total; (c) complexitat temporal de cadascuna; (d) què passa a la pràctica en cridar-les amb una llista de 10.000 trams?

(a) Espai auxiliar. Totes dues versions fan n+1 crides imbricades, així que totes dues paguen una pila de profunditat Θ(n) (02-02: cada marc de la pila compta com a espai auxiliar). Però la versió amb slice paga a més una còpia per crida: ocupacio[1:] crea una llista nova de n−1 elements, la crida següent en crea una altra de n−2, etc. I aquí hi ha el punt important: mentre la recursió és al seu punt més profund, totes aquestes còpies estan vives alhora (cadascuna és argument d'un marc que encara no ha retornat). Total: (n−1) + (n−2) + … + 1 ≈ n²/2 → espai auxiliar Θ(n²). La versió amb índexs no copia res: només la pila, Θ(n) auxiliar.

(b) Espai total = entrada + auxiliar (02-02). Amb slice: Θ(n) + Θ(n²) = Θ(n²). Amb índexs: Θ(n) + Θ(n) = Θ(n).

(c) Temps. L'slice no només ocupa: també triga O(longitud) a copiar-se (02-01). La versió slice paga la mateixa sèrie aritmètica en temps: Θ(n²). La versió amb índexs: Θ(n).

(d) Cap de les dues no sobreviu a 10.000 elements: Python limita la profunditat de recursió a ~1000 per defecte, així que totes dues llancen RecursionError molt abans que la memòria sigui el problema. Com vam veure a 01-02 en comparar iteratiu i recursiu, quan la recursió és purament lineal, un bucle (o sum(ocupacio)) fa la mateixa feina amb pila O(1).

Errors típics: (1) oblidar que l'slice copia (sembla un accés, però és una llista nova); (2) comptar només "un marc de pila" en lloc de la profunditat màxima simultània; (3) confondre espai auxiliar amb total i reportar Θ(n²) per a la versió amb índexs "perquè l'entrada més la pila sumen molt" — l'entrada és Θ(n) i la pila Θ(n): total Θ(n).

Dificultat: mitjana

A cada fitxatge, RutaBus valida el bitllet contra la llista de bitllets actius:

Les dades d'explotació diuen que el 90 % dels fitxatges són vàlids, i que els bitllets vàlids apareixen en posicions uniformement distribuïdes de la llista. El 10 % restant són bitllets invàlids (no són a la llista).

Preguntes: (a) millor cas i pitjor cas, amb la notació adequada; (b) nombre esperat de comparacions amb aquesta distribució, i el Θ del cas mitjà; (c) si el percentatge d'invàlids pugés al 99 %, canviaria el Θ del cas mitjà?

(a) Millor cas: el bitllet és el primer de la llista → 1 comparació → Θ(1). Pitjor cas: el bitllet és l'últim o no hi és → n comparacions → Θ(n). Fixa't que fem servir Θ del cas, com vam precisar a 02-03: cada cas té la seva fita ajustada.

(b) És exactament l'esquema de la cerca lineal de 02-03, però amb la distribució donada. Si el bitllet és vàlid i és en posició uniforme, el nombre mitjà de comparacions és (1 + 2 + … + n)/n = (n+1)/2. Si és invàlid, sempre són n. Esperança total:

E[comparacions] = 0,9 · (n+1)/2 + 0,1 · n = 0,45n + 0,45 + 0,1n = 0,55n + 0,45

Això és Θ(n): una recta amb pendent 0,55, però una recta al capdavall.

(c) Amb un 99 % d'invàlids: E = 0,01 · (n+1)/2 + 0,99 · n ≈ 0,995n. La constant gairebé es duplica respecte del cas anterior (0,55 → 0,995), cosa que en producció es nota, però el Θ no canvia: continua sent Θ(n). Aquesta és la lliçó de 02-03: la distribució d'entrades mou les constants del cas mitjà, i només de vegades mou l'ordre.

Error típic: escriure "el cas mitjà és Θ(n/2), que és millor que Θ(n)". Θ(n/2) és Θ(n) — la notació asimptòtica no distingeix constants (01-03). Si vols comunicar la constant, digues "≈ 0,55n comparacions", no t'inventis un Θ nou.

Dificultat: mitjana

L'equip de RutaBus va mesurar quatre funcions (F1–F4) amb entrades de mida creixent i va obtenir aquests temps (mil·lisegons):

I aquests són els quatre codis, sense dir quin és quin:

Aparella A, B, C i D amb F1, F2, F3 i F4, raonant a partir de com escala el temps en duplicar n, i assigna a cadascuna el seu Θ.

Pista: en duplicar n, un Θ(n) duplica el seu temps, un Θ(n²) el quadruplica, un Θ(log n) hi suma una quantitat fixa minúscula i un Θ(1) ni s'immuta. És la jerarquia de 01-03 vista des del cronòmetre.

Apliquem l'heurística de duplicació:

• F1: 0,8 → 1,6 → 3,2. Es duplica en duplicar n: creixement lineal, Θ(n). És C, que recorre la llista una vegada per sumar.
• F2: constant, 0,0004 sempre: Θ(1). És A: un accés a matriu per índexs no depèn de n.
• F3: 90 → 360 → 1.440. Es quadruplica en duplicar: Θ(n²). És D, el bucle dependent de parells (n(n−1)/2 iteracions, Exercici 1).
• F4: 0,0011 → 0,0012 → 0,0013. Suma una quantitat fixa diminuta en duplicar n: Θ(log n). És B: cada volta del while redueix l'interval a la meitat, així que hi ha ~log₂ n voltes.

Errors típics: (1) comparar valors absoluts entre columnes ("F3 és la més lenta, per tant és la pitjor funció") — el que importa és com escala, no quant val en un n concret: per a n petit un Θ(n²) pot guanyar un Θ(n) amb constant gran; (2) confondre Θ(log n) amb Θ(1) perquè "gairebé no creix" — creix, i la diferència importa quan n té nou xifres.

Dificultat: alta

Aquesta funció genera l'informe diari d'incidències de la xarxa. El seu autor assegura que "és un sol bucle, així que és O(n)". La teva feina: (a) dir quina és la complexitat real; (b) assenyalar cada cost ocult amb la seva línia i el seu cost individual; (c) justificar el total. No cal arreglar-la (això és matèria de 06-03): només diagnosticar-la amb precisió.

(a) La complexitat real és Θ(n²), no Θ(n).

(b) Hi ha dos costos ocults, tots dos vistos a 02-01:

• Línia A — inc in processades: cerca lineal sobre una llista que creix. A la iteració i, processades té fins a i elements, així que la comprovació costa O(i). Sumant: 0 + 1 + … + (n−1) = n(n−1)/2 → Θ(n²) només aquesta línia.
• Línia B — informe = informe + ...: les cadenes de Python són immutables; cada concatenació crea una cadena nova copiant tot l'anterior. Si l'informe arriba a tenir L caràcters, el cost acumulat de reconstruir-lo trosset a trosset és Θ(L²) — i L és proporcional a n, així que també Θ(n²).

(L'split(";") de cada línia és O(longitud de la cadena), que tractem com a constant si les incidències tenen mida acotada — aquest no és un cost ocult problemàtic.)

(c) Total: Θ(n²) + Θ(n²) = Θ(n²). El "un sol bucle, per tant O(n)" falla perquè l'anàlisi línia a línia exigeix el cost de cada operació interna, i aquí dues operacions d'aparença innocent (un in i un +) amaguen recorreguts complets d'estructures que creixen amb n.

Error típic: detectar un dels dos costos i donar l'anàlisi per acabada. En codi real els costos ocults vénen en grup, perquè el mateix estil de programació (acumular sobre llista/cadena i consultar amb in) els produeix tots alhora. Acostuma't a auditar cada operació del cos del bucle.

Has exercitat el cicle complet d'anàlisi del Mòdul 2: derivar Θ comptant iteracions (bucles simples, imbricats i dependents amb el seu n(n−1)/2), desemmascarar els costos ocults de Python (in sobre llista, insert(0), slices que copien, concatenació de cadenes), distingir espai auxiliar de total (amb la pila de recursió inclosa), separar millor/pitjor/mitjà amb distribucions concretes, i llegir ordres de creixement directament en una taula de mesures amb l'heurística de duplicació.

Si algun exercici se t'ha resistit, torna a la lliçó corresponent (02-01 per a temps i costos ocults, 02-02 per a espai, 02-03 per a casos) i reintenta'l demà: l'anàlisi de complexitat és d'aquelles habilitats que es consoliden a la segona passada. A la lliçó següent canviem de múscul: d'analitzar codi donat a dissenyar algorismes nous amb les quatre estratègies del Mòdul 3.