A les dues lliçons anteriors vam analitzar temps i espai "assumint el pitjor cas", i diverses vegades ens vam creuar amb funcions que de vegades acaben de seguida i de vegades recorren tota l'entrada: hi_ha_duplicades tallava en trobar el primer duplicat, totes_abans_b en trobar la primera arribada tardana. Aquesta lliçó posa nom i mètode a aquesta observació: un mateix algorisme pot tenir costos molt diferents segons quina entrada rebi, no només segons la seva mida. Aprendrem a definir i calcular el millor cas, el pitjor cas i el cas mitjà, a decidir quin importa segons el context (no és el mateix per a una app mòbil que per a un sistema de frenada), a relacionar-los correctament amb les notacions O/Ω/Θ — desmuntant un mite molt estès — i a entendre de manera intuïtiva l'anàlisi amortitzada, aquell "O(1) amortitzat" que vam deixar pendent a la taula de costos de Python de 02-01.

1. Un algorisme, moltes entrades: els tres casos
2. Els tres casos de cerca_parada
3. Quin cas importa? Depèn del context
4. Casos i notacions: desmuntant el mite "O = pitjor cas"
5. Anàlisi amortitzada: el cas de list.append
6. Exemple integrador: validar els horaris de RutaBus

Fins ara escrivíem T(n) com si la mida n determinés el cost. Però per a molts algorismes no és així: dues entrades de la mateixa mida poden costar molt diferent. Cercar "Plaça Major" en una línia de 40 parades costa 1 comparació si és la primera parada i 40 si és l'última. La mida és idèntica; el cost, no.

Per això l'anàlisi es desdobla en tres preguntes, totes tres sobre entrades de mida n:

• Millor cas: de totes les entrades de mida n, quant costa la més favorable? És el terra de l'algorisme: mai no anirà més ràpid.
• Pitjor cas: quant costa l'entrada més desfavorable? És el sostre: una garantia absoluta, passi el que passi.
• Cas mitjà: si les entrades arriben segons una distribució donada (típicament "totes igual de probables"), quant costa de mitjana? És l'expectativa realista a llarg termini.

Tres detalls de la definició que eviten confusions més endavant:

1. Els tres casos es refereixen a l'entrada, no a la sort de l'algorisme: el millor cas d'una cerca no és "tenir un ordinador ràpid", és "que allò cercat sigui a la primera posició".
2. Tots tres són funcions de n: T_millor(n), T_pitjor(n), T_mitja(n). El millor cas de cercar en 40 parades i en 4.000 és "és la primera", però continua sent una funció (constant) de la mida.
3. El cas mitjà exigeix declarar una distribució de probabilitat sobre les entrades ("la parada cercada pot ser a qualsevol posició amb la mateixa probabilitat"). Si la distribució suposada no s'assembla a la realitat, la mitjana calculada tampoc.

Apliquem-ho a la cerca lineal de la lliçó 01-02, la que fa servir RutaBus per localitzar una parada en una línia:

Operació bàsica: la comparació parada == nom. Sigui n = len(linia).

Millor cas — O(1). L'entrada més favorable: nom és a la primera posició. Una comparació i return. T_millor(n) = 1, constant: Θ(1), sigui quina sigui n.

Pitjor cas — O(n). Les entrades més desfavorables: nom és a l'última posició (n comparacions) o no hi és (n comparacions i return -1). T_pitjor(n) = n: Θ(n). És la garantia que donàvem per defecte a 02-01.

Cas mitjà — O(n). Suposem que la parada és a la línia i que cadascuna de les n posicions és igual de probable (probabilitat 1/n cadascuna). Si és a la posició i (comptant des d'1), costen i comparacions. El cost mitjà és la mitjana de tots els escenaris ponderada per la seva probabilitat:

El numerador és la nostra vella amiga la suma aritmètica (02-01): n(n+1)/2. Dividint entre n:

De mitjana, la cerca recorre mitja línia. I asimptòticament? n/2 és lineal — les constants es descarten (01-03) —, així que el cas mitjà és Θ(n), el mateix ordre que el pitjor cas. És un resultat molt instructiu: "el doble de ràpid a la pràctica" i "del mateix ordre en teoria" són afirmacions compatibles. I si les cerques fallides fossin freqüents (usuaris que escriuen malament el nom), la mitjana real s'acostaria encara més a n — recorda: la mitjana depèn de la distribució que declaris.

Resum:

Les tres anàlisis existeixen perquè responen a necessitats diferents. La pregunta correcta no és "quin és el bo?" sinó "què necessito garantir?":

Regles pràctiques:

• El pitjor cas és l'anàlisi per defecte (per això el vam assumir a 02-01): és l'únic que dona una garantia incondicional, sol ser el més fàcil de calcular i mai no peca d'optimista.
• El cas mitjà és el més informatiu quan hi ha volum: a un servei que atén un milió de cerques al dia li importa el cost mitjà × un milió, no la cerca concreta més lenta. La seva feblesa: depèn d'una distribució suposada que pot no complir-se.
• El millor cas, aïllat, és gairebé propaganda: "el meu algorisme pot acabar en O(1)" no compromet a res (també cerca_parada pot!). Només és valuós quan saps que les entrades favorables són les freqüents al teu sistema.

L'exemple cèlebre d'aquesta tensió és quick sort (l'estudiarem a 04-04): cas mitjà O(n log n) excel·lent que el fa dominar a la pràctica, pitjor cas O(n²) que obliga a prendre precaucions. Bona part de l'enginyeria d'algorismes consisteix a gestionar aquesta bretxa entre cas mitjà i pitjor cas.

Circula per internet (i per algun material de formació antic — inclosa una versió anterior d'aquest curs) una simplificació falsa:

❌ "O gran descriu el pitjor cas, Ω el millor cas i Θ el cas mitjà."

No. Són dos eixos independents que es combinen:

• Els casos (millor / pitjor / mitjà) trien quina funció de cost estem mesurant: T_millor(n), T_pitjor(n) o T_mitja(n). Parlen d'entrades.
• Les notacions (O / Ω / Θ, lliçó 01-03) descriuen com creix una funció: fita superior, fita inferior o fita ajustada. Parlen de funcions, sigui quina sigui.

Qualsevol notació es pot aplicar a qualsevol cas. Totes aquestes frases sobre cerca_parada són correctes i signifiquen coses diferents:

D'on ve, la confusió? D'un ús col·loquial legítim: com que T_millor(n) ≤ T(n) ≤ T_pitjor(n) per a tota entrada, dir "l'algorisme és O(n)" a seques sol voler dir "ni tan sols el seu pitjor cas supera el lineal", i "és Ω(1)" sol referir-se al fet que el seu millor cas és constant. La drecera és còmoda, però fusiona els dos eixos i acaba produint el mite. Dues conseqüències pràctiques de tenir-ho clar:

• El més informatiu és Θ aplicada a un cas concret: "pitjor cas Θ(n), millor cas Θ(1)" diu més que qualsevol O solta.
• Frases com "la cerca lineal és O(n²)" són tècnicament certes (una fita superior fluixa continua sent fita superior, com vam veure a 01-03) però inútils. Si algú et dona només una O, pregunta't: de quin cas parla, i és una fita ajustada?

A la taula de costos de 02-01 vam escriure que llista.append(x) és "O(1) amortitzat", i vam prometre explicar-ho aquí. L'anàlisi amortitzada és una quarta perspectiva, diferent de les tres anteriors: no fa la mitjana sobre entrades possibles, sinó sobre una seqüència d'operacions executades de debò, una rere l'altra.

El problema: una llista de Python guarda els seus elements en un bloc de memòria contigu amb una capacitat fixa. Mentre quedi lloc, append escriu al final: O(1) autèntic. Però quan el bloc s'omple, Python en reserva un altre de més gran (aproximadament un 12,5% més, més un marge) i copia tots els elements: aquell append concret costa O(n).

És, doncs, append O(n)? Mirant una operació aïllada en el seu pitjor cas, sí. Però és una resposta enganyosa, perquè les operacions cares no poden passar seguides: després de cada còpia costosa, la capacitat sobrant garanteix molts appends barats abans de la següent. La comptabilitat honesta mira la seqüència completa:

• Inserir n elements començant per una llista buida dispara redimensionaments de mides que creixen geomètricament (cadascun un factor més gran que l'anterior).
• La suma de totes les còpies de tots els redimensionaments és proporcional a n — una sèrie geomètrica es comporta com el seu últim terme, no com la suma aritmètica de 02-01.
• Cost total: n appends barats + O(n) de còpies acumulades = O(n). Repartit entre les n operacions: O(1) per operació.

Això vol dir "O(1) amortitzat": garantia sobre el total de la seqüència — n appends costen O(n), segur, sense suposicions probabilístiques —, encara que alguna operació solta sigui cara. Una metàfora comptable: cada append barat "paga" un petit recàrrec que queda estalviat per finançar la còpia futura; quan la còpia arriba, el fons la cobreix.

En què es diferencia del cas mitjà, que és amb el que més es confon:

Avís pràctic: "amortitzat" garanteix el total, no cada operació individual. A l'exemple de les arribades en temps real, un append ocasional lent és invisible; en un sistema de temps real estricte (taula de l'apartat 3), aquest pic aïllat pot ser inacceptable encara que la mitjana sigui perfecta — una altra vegada, saber què garanteix cada anàlisi és el que permet triar bé.

Tanquem el mòdul ajuntant-ho tot. L'equip d'operacions de RutaBus carrega cada nit el fitxer d'horaris de l'endemà: una taula on cada fila és (linia, parada, hora). Abans de publicar-la cal validar-la: cap hora no pot estar mal formada.

Anàlisi completa, amb n = nombre de files:

• Millor cas — Θ(1): la primera fila ja és invàlida (per exemple ("L1", "Plaça Major", "25:70")). Una comprovació i fora. Fixa't en la ironia: el millor cas de l'algorisme és el pitjor dia de l'operador.
• Pitjor cas — Θ(n): el fitxer és completament vàlid — cal mirar-lo sencer per poder garantir-ho — o l'únic error és a l'última fila. I aquest és el cas que importa aquí: el procés nocturn ha de tenir un marge reservat suficient totes les nits, i les nits normals (fitxer correcte) són precisament les de cost màxim.
• Cas mitjà: depèn de la distribució d'errors. Si les files són vàlides amb una probabilitat molt alta (el normal en producció), el cas típic ≈ el pitjor: Θ(n). Si el fitxer vingués ple d'errors primerencs, la mitjana baixaria — però planificar la finestra nocturna amb aquesta esperança seria mala enginyeria: per dimensionar, pitjor cas.
• Espai (02-02): variables escalars reutilitzades, sense còpies ni estructures: auxiliar O(1). Un validador es pot permetre llegir i descartar.
• I si a més el validador acumulés les files correctes en una llista de sortida amb append, aquest cost seria O(1) amortitzat per fila: total Θ(n) garantit.

Un sol algorisme de deu línies i hem fet servir tot el mòdul: anàlisi línia a línia, casos, notacions ben aplicades, espai i amortització.

• Repetir el mite "O = pitjor cas, Ω = millor cas": els casos trien la funció a mesurar; les notacions en descriuen el creixement. Es combinen lliurement: "millor cas O(1)" i "pitjor cas Ω(n)" són frases perfectament formades.
• Confondre millor cas amb entrada petita: el millor cas no és "n = 1"; és l'entrada de mida n més favorable. Els tres casos són funcions de n.
• Donar un cas mitjà sense declarar la distribució: "de mitjana n/2" pressuposa posicions equiprobables i que l'element hi és. Canvia la premissa (moltes cerques fallides) i canvia la mitjana. Sense distribució explícita, una mitjana no afirma res.
• Vendre el millor cas: "pot arribar a O(1)" és cert per a gairebé qualsevol cerca amb sortida anticipada i no garanteix res. Sospita de qualsevol anàlisi que només esmenti l'escenari favorable.
• Llegir "amortitzat" com a "sempre": O(1) amortitzat promet el total de la seqüència, no cada operació; alguna pot ser O(n). Irrellevant en una app, decisiu en temps real.
• Consell: en analitzar un algorisme amb sortides anticipades (return dins del bucle), pregunta't sistemàticament tres coses: quina entrada em fa sortir a la primera? (millor cas), quina m'obliga a arribar al final? (pitjor cas), com arriben les entrades al meu sistema? (cas que he d'optimitzar).

Exercici 1. RutaBus comprova si dos usuaris poden compartir trajecte verificant si les seves línies tenen alguna parada comuna, amb la versió O(n²) de 02-01:

Suposant len(linia_a) = len(linia_b) = n, descriu l'entrada del millor cas i la del pitjor cas, i dona l'ordre de cadascun.

Exercici 2. Classifica cada afirmació com a certa o falsa, justificant-ho amb els dos eixos (casos vs notacions): a) "El millor cas de cerca_parada és O(n)." b) "El pitjor cas de cerca_parada és Ω(n)." c) "cerca_parada és Θ(n) per a tota entrada." d) "El cas mitjà de cerca_parada és O(n²)."

Exercici 3. El panell d'una parada manté les arribades en una llista ordenada per hora inserint cada nova arribada al seu lloc:

Amb la taula de costos de 02-01: (a) dona el millor i el pitjor cas de registra_arribada i quina entrada els provoca; (b) raona si insert pot presumir d'"O(1) amortitzat" com append, o no, i per què.

Solució 1. Millor cas Θ(n) — compte, no Θ(1): l'entrada més favorable és que la primera parada de linia_a sigui a linia_b... però trobar-la amb in pot costar fins a n comparacions; el cas rigorosament òptim és que a més sigui la primera de linia_b: 1 comparació, Θ(1). Aquest exercici ensenya a definir el millor cas amb precisió: l'entrada òptima és "la primera d'A coincideix amb la primera de B" → Θ(1); "la primera d'A és a B (on sigui)" ja pot costar Θ(n). Pitjor cas Θ(n²): no comparteixen cap parada — les n voltes del bucle extern paguen n comparacions cadascuna, sense sortida anticipada possible. Fixa't que el pitjor cas és justament la resposta "False", igual que a horari_valid el pitjor cas era el fitxer vàlid: verificar l'absència obliga a mirar-ho tot.

Solució 2. a) Certa. El millor cas és Θ(1), i tota funció Θ(1) és també O(n): una fita superior fluixa és vàlida (encara que poc informativa). La frase és correcta; útil, no. b) Certa. El pitjor cas costa exactament n comparacions, per tant està fitat inferiorment per una cosa lineal: Ω(n). I també és O(n); per això el més ajustat és dir Θ(n). c) Falsa. Per a l'entrada amb la parada a la primera posició el cost és 1, que no és Θ(n). Precisament perquè els casos difereixen, l'algorisme en conjunt no té una Θ única — cal donar-la a cada cas. d) Certa però inútil. El cas mitjà és Θ(n) i per tant també O(n²): fita superior certa i fluixa. És l'exemple canònic de per què "és O(alguna cosa)" sense més pot ser una dada buida.

Solució 3. (a) La cerca amb bisect costa O(log n) sempre. El cost variable és a insert: desplaça tots els elements posteriors a la posició. Millor cas: l'arribada és la més tardana i va al final — 0 desplaçaments — → Θ(log n) total. Pitjor cas: l'arribada és la més primerenca i va al principi — n desplaçaments → Θ(n) total. (b) No: l'amortització d'append funciona perquè les operacions cares (redimensionar) són necessàriament escasses i les barates les prefinancen. Amb insert no existeix aquest mecanisme: cada inserció al principi costa O(n) sempre, i una seqüència adversa (arribades en ordre invers, de la més tardana a la més primerenca... o un atacant, taula de l'apartat 3) fa que totes les operacions siguin cares: n insercions → suma aritmètica → Θ(n²) total, és a dir Θ(n) per operació també en termes amortitzats. "Amortitzat" no és cap encanteri: cal demostrar que les operacions cares no es poden repetir.

Amb aquesta lliçó completem l'arsenal de l'anàlisi d'algorismes. Hem après que el cost no depèn només de la mida de l'entrada sinó de l'entrada mateixa, i a mesurar-lo amb tres vares diferents sobre cerca_parada: millor cas Θ(1), pitjor cas Θ(n) i cas mitjà ≈ n/2 → Θ(n); hem vist que l'elecció del cas és una decisió d'enginyeria — pitjor cas per a garanties, temps real i entrades hostils; cas mitjà per al rendiment típic amb volum; millor cas només quan el favorable és el freqüent —; hem desmuntat el mite "O = pitjor cas, Ω = millor cas" separant els dos eixos (els casos trien quina funció mesurar, les notacions descriuen com creix); hem afegit l'anàlisi amortitzada amb list.append — garantia sobre la seqüència completa, sense probabilitats —; i ho hem integrat tot validant els horaris nocturns de RutaBus, on el pitjor cas (el fitxer correcte) resulta ser el dia normal. Juntament amb l'anàlisi temporal línia a línia (02-01) i l'espacial (02-02), ja sabem respondre amb rigor a la pregunta "quant costa aquest algorisme?" en totes les seves variants.

Però saber mesurar algorismes no és el mateix que saber crear-los. Fins ara hem analitzat solucions ja escrites; la pregunta natural següent és: davant d'un problema nou de RutaBus — planificar el trajecte òptim entre dues parades, assignar autobusos a línies, quadrar horaris —, com es dissenya un bon algorisme des de zero? Al Mòdul 3 estudiarem les quatre grans estratègies de disseny que ja van treure el cap a 01-02: divideix i venceràs (03-01), algorismes voraços (03-02), programació dinàmica (03-03) — on retrobarem, amb nom propi, la idea de gastar memòria per no repetir feina que vam apuntar a 02-02 — i backtracking (03-04). I cada disseny que fem, el sotmetrem al judici de les eines que aquest mòdul ens ha donat.