Ja sabem què és un algorisme i quins tipus n'existeixen; ara necessitem un llenguatge rigorós per respondre la pregunta clau del curs: quin d'aquests dos algorismes és més eficient?. Aquest llenguatge és la notació asimptòtica: una manera de descriure com creix el cost d'un algorisme a mesura que creix la mida de la seva entrada, sense dependre de l'ordinador, del llenguatge ni del cronòmetre. Dominar-la és imprescindible: la farem servir a cada lliçó restant del curs, apareix a tota la documentació tècnica seriosa (has vist "O(1) average" a la documentació dels diccionaris de Python?) i és pregunta fixa en entrevistes tècniques.

1. Per què mesurar el creixement i no el temps de rellotge
2. La idea central: com escala el cost amb n
3. O gran, Ω i Θ: què significa cadascuna
4. Jerarquia d'ordres comuns amb la xarxa de RutaBus
5. Regles pràctiques de simplificació
6. Què ve després: el Mòdul 2

La primera temptació en comparar algorismes és cronometrar-los. Fem l'experiment mental amb RutaBus: dos desenvolupadors implementen la cerca d'una parada per nom i mesuren el temps amb 10.000 parades.

És millor l'algorisme d'A? No ho podem saber amb aquestes dades. El temps de rellotge barreja massa coses alienes a l'algorisme:

• El maquinari: CPU, memòria cau, disc... La mateixa cerca lineal pot ser 50 vegades més ràpida en una màquina que en una altra.
• El llenguatge i la seva implementació: Python interpretat vs C compilat; fins i tot versions diferents de Python.
• L'estat del sistema: altres processos, el sistema operatiu, la sort.
• La mida d'entrada triada: amb 10 parades gairebé qualsevol algorisme sembla instantani; les diferències esclaten quan les dades creixen.

El que sí que és una propietat de l'algorisme (i no de la màquina) és quantes operacions bàsiques necessita en funció de la mida de l'entrada, n. Si repetim l'experiment variant n (el nombre de parades), el panorama canvia:

La màquina ràpida d'A li dona avantatge amb n petit, però cap màquina no compensa una diferència de creixement: al milió de parades, l'algorisme de B fa 50.000 vegades menys feina. La notació asimptòtica captura exactament això: el ritme de creixement del cost quan n es fa gran, ignorant factors constants que depenen de la màquina.

Anomenem n la mida de l'entrada (nombre de parades de la xarxa, nombre d'horaris a ordenar...) i f(n) el nombre d'operacions bàsiques que realitza l'algorisme per a aquesta entrada. La pregunta asimptòtica és: quan n es duplica, què li passa a f(n)?

• Si f(n) = 3n + 5, en duplicar n el cost aproximadament es duplica: creixement lineal.
• Si f(n) = n², en duplicar n el cost es multiplica per 4: creixement quadràtic.
• Si f(n) = 20 (no depèn de n), el cost no canvia: creixement constant.

Fixa't que el "3" i el "+5" de la primera funció amb prou feines importen per a aquesta pregunta: 3n + 5 i 900n + 2000 es comporten igual qualitativament (duplicar n ≈ duplicar cost), tot i que una sigui 300 vegades més lenta que l'altra. Aquest factor 300 és el que absorbeix la màquina, el llenguatge, etc.; el tipus de creixement, no. Per això la notació asimptòtica descarta constants i es queda amb la forma de la corba.

Les tres notacions expressen fites sobre el creixement de f(n). Definició semiformal i, sobretot, el seu significat pràctic:

Diem que f(n) és O(g(n)) si, a partir de certa mida d'entrada, f(n) queda per sota de g(n) multiplicada per alguna constant. Formalment: existeixen constants c > 0 i n₀ tals que f(n) ≤ c·g(n) per a tot n ≥ n₀.

Traducció pràctica: "el cost de l'algorisme no creix més ràpid que g(n)". És una garantia cap amunt: per això és la notació més usada, ja que als enginyers ens interessa fitar el pitjor comportament possible.

Exemple: la cerca lineal d'una parada fa com a màxim n comparacions → és O(n). Nota tècnica: també seria formalment correcte dir que és O(n²) (una fita superior més folgada), però per convenció es dona sempre la fita més ajustada coneguda.

Diem que f(n) és Ω(g(n)) si, a partir de cert n, f(n) queda per sobre de c·g(n) per a alguna constant c > 0.

Traducció pràctica: "el cost no pot ser menor que aquest ordre". Serveix per expressar límits del que és possible. Exemple: qualsevol algorisme que hagi de mostrar totes les parades de la xarxa és Ω(n) — no hi ha manera de llistar n coses sense com a mínim n passos.

Diem que f(n) és Θ(g(n)) si és alhora O(g(n)) i Ω(g(n)): el cost queda atrapat entre dos múltiples de g(n).

Traducció pràctica: "el cost creix exactament al ritme de g(n)". És la caracterització més informativa quan es pot donar. Exemple: comptar les parades d'una llista recorrent-la sencera és Θ(n): ni més ni menys que un pas per parada.

Un matís que convé deixar apuntat: aquestes notacions descriuen el creixement d'una funció de cost, i un mateix algorisme pot tenir funcions de cost diferents segons si l'entrada li és favorable o no (la cerca lineal troba "Plaça Major" a la primera si és al principi de la llista...). Aquesta anàlisi per millor cas, pitjor cas i cas mitjà té la seva pròpia lliçó (02-03); de moment, quan diguem que un algorisme "és O(n)" ens referirem al seu comportament en el pitjor dels casos, que és l'ús més habitual de la O gran.

Aquests són els ordres de creixement que trobaràs una vegada i una altra, de millor a pitjor:

Els noms prenen vida amb nombres concrets. Suposem que cada operació costa 1 microsegon (una milionèsima de segon) i fem servir com a n el nombre de parades de la xarxa de RutaBus:

Lectures importants d'aquesta taula:

• O(log n) és gairebé tan bo com O(1): passar de 10 a 100.000 parades només multiplica el cost per ~6. Duplicar n afegeix una operació. Per això la cerca binària és tan valuosa.
• O(n log n) escala molt bé: ordenar 100.000 horaris costa menys de 2 segons. És l'ordre dels bons algorismes d'ordenació.
• O(n²) esdevé inviable sorprenentment aviat: amb la xarxa d'una gran ciutat (100.000 parades), calcular totes les distàncies entre parells trigaria hores. Un algorisme quadràtic que "anava bé en proves" amb 100 parades pot enfonsar l'aplicació en producció.
• O(2ⁿ) és intractable llevat de n minúscul: amb només 100 elements, l'univers no ha existit prou temps per acabar el càlcul. Quan un problema només admet solucions exponencials exactes, entren en joc les heurístiques que vam veure a la lliçó anterior.

Com a referència ràpida en Python (el perquè exacte de cada cost s'analitza al Mòdul 2):

Quan expressem el cost d'un algorisme, la notació asimptòtica se simplifica amb dues regles mecàniques:

Els factors constants depenen de la màquina i del llenguatge, no de l'algorisme, així que s'eliminen:

• 5n → O(n)
• n/2 → O(n) (dividir per 2 és multiplicar per la constant 0,5)
• 300 → O(1) (qualsevol cost fix, per gran que sigui, és constant)

Compte: això no vol dir que les constants no importin a la vida real. Entre dos algorismes O(n), el de constant petita guanya; la notació només diu que aquest matís no canvia la forma del creixement. Reprendrem aquesta tensió al Mòdul 5 (optimització).

Quan el cost és una suma de termes, per a n gran un d'ells "engoleix" els altres — el que creix més ràpid segons la jerarquia que acabem de veure:

• n² + 10n + 500 → O(n²)
• n log n + n → O(n log n)
• 2ⁿ + n³ → O(2ⁿ)

Per què és legítim? Comprova-ho amb nombres: per a n = 10.000, n² = 100.000.000 mentre que 10n + 500 = 100.500 — menys del 0,1% del total. Com més gran és n, més irrellevant és el terme menor.

Una funció de RutaBus fa el següent amb una xarxa de n parades:

1. Llegeix la configuració de l'app → cost fix: 25 operacions.
2. Ordena les parades alfabèticament → n log n operacions.
3. Recorre la llista ordenada per marcar les accessibles → n operacions.
4. Comprova les 2 parades preferides de l'usuari → 2 operacions.

Cost total: f(n) = n log n + n + 27. Aplicant les regles: descartem les constants (27) i ens quedem amb el terme dominant (n log n engoleix n). Resultat: O(n log n).

Taula de pràctica ràpida:

Amb la notació asimptòtica ja sabem expressar l'eficiència d'un algorisme. El que encara no hem fet és derivar-la a partir del codi: mirar una funció Python línia a línia, comptar-ne les operacions i els bucles, i concloure "això és O(n²)". Aquest és exactament l'objectiu de la propera lliçó (02-01, complexitat temporal). Després el Mòdul 2 completa el quadre amb la complexitat espacial (quanta memòria consumeix un algorisme, 02-02) i l'anàlisi per millor cas, pitjor cas i cas mitjà (02-03), que aquí només hem deixat apuntada.

• Comparar algorismes cronometrant-los en una sola màquina i amb una sola mida d'entrada. El benchmark té el seu lloc (Mòdul 5), però la conclusió "A és millor que B" només és sòlida si compares creixements. Consell: si mesures, mesura amb diversos n creixents (n, 2n, 4n...) i observa com escala cadascun.
• Creure que la O gran descriu el temps exacte. O(n) no diu "triga n segons" ni "fa exactament n operacions"; diu que el cost creix com a màxim linealment. Dos algorismes O(n) poden diferir en un factor 100.
• Ignorar les constants quan n és petit. Per a n = 20, un O(n²) simple pot guanyar un O(n log n) sofisticat. L'asimptòtica mana quan n creix; amb dades minúscules, mesura.
• Fer servir O, Ω i Θ com a sinònims. Dir "aquest algorisme és Ω(n²)" afirma que costa com a mínim n² — probablement volies dir O(n²) (com a màxim) o Θ(n²) (exactament). Revisa quina fita vols expressar.
• Sumar en lloc de quedar-se amb el dominant... o al revés. Els passos seqüencials se sumen i després domina el més gran: O(n) seguit de O(n log n) és O(n log n), no O(n · n log n). La multiplicació apareix amb bucles niats, que analitzarem a 02-01.
• Pensar que "asimptòtic" és teoria irrellevant. Les taules de creixement mostren el contrari: la diferència entre O(n²) i O(n log n) és la diferència entre una app que respon a l'instant i una que es penja quan la ciutat afegeix parades.

Simplifica al seu ordre asimptòtic (O gran) cadascuna d'aquestes funcions de cost, indicant quina regla apliques:

a) f(n) = 4n + 90 b) f(n) = n²/10 + 50n + 3 c) f(n) = 1000 d) f(n) = 2n log n + n² + 7n e) f(n) = log n + 25

La xarxa de RutaBus creixerà de 1.000 a 100.000 parades (multiplicar-se per 100). Per a cadascun d'aquests tres algorismes, calcula (aproximadament) per quant es multiplicarà el seu nombre d'operacions, i decideix quins continuaran sent viables si avui triguen 1 ms amb 1.000 parades:

a) Algorisme X: O(n) b) Algorisme Y: O(n²) c) Algorisme Z: O(log n) — fes servir log₂(1.000) ≈ 10 i log₂(100.000) ≈ 17

Indica si cada afirmació és vertadera o falsa i justifica-ho:

a) Un algorisme O(n²) sempre triga més que un O(n), per a qualsevol entrada. b) Si un algorisme és Θ(n), llavors també és O(n) i Ω(n). c) Mostrar per pantalla les n parades de la xarxa es pot fer en O(log n). d) f(n) = 5n + 20 és O(n²).

Solució 1:

a) O(n) — regla 1: es descarten la constant multiplicativa 4 i l'additiva 90. b) O(n²) — regla 2: n² domina 50n; regla 1: es descarten l'1/10 i el 3. c) O(1) — un cost fix, per gran que sigui, és constant. d) O(n²) — regla 2: a la jerarquia, n² creix més ràpid que n log n, així que domina. e) O(log n) — la constant 25 es descarta; queda el terme logarítmic.

Solució 2:

a) X (O(n)): el cost escala linealment → ×100. D'1 ms passaria a ~100 ms. Viable, tot i que comença a notar-se. b) Y (O(n²)): el cost escala amb el quadrat → ×100² = ×10.000. D'1 ms passaria a ~10 segons. Inviable per a una operació interactiva de l'app. c) Z (O(log n)): el cost passa de ~10 a ~17 unitats → ×1,7. D'1 ms passaria a ~1,7 ms. Perfectament viable: aquesta és la màgia del creixement logarítmic.

Solució 3:

a) Falsa. La notació descriu el creixement per a n gran, no el temps per a tota entrada: amb n petit, les constants poden fer que l'O(n²) guanyi (p. ex., 2n² davant de 1000n per a n < 500). El que sí que és cert: a partir d'algun n, l'O(n) sempre acaba guanyant. b) Vertadera. És la definició de Θ: fita ajustada vol dir ser alhora fita superior (O) i inferior (Ω) del mateix ordre. c) Falsa. Produir n línies de sortida exigeix com a mínim n operacions: el problema és Ω(n), i cap astúcia algorísmica no pot baixar d'aquí. d) Vertadera, però enganyosa. Formalment 5n + 20 ≤ n² a partir de cert n, així que l'afirmació compleix la definició de O. Tanmateix, la fita ajustada és O(n) — i per convenció sempre es dona la més ajustada coneguda. Aquest matís (que O és només una fita superior) és la font de l'error de fer-la servir com si fos Θ.

En aquesta lliçó hem adquirit el llenguatge amb què es parla d'eficiència en informàtica. Hem vist per què el temps de rellotge no serveix per comparar algorismes (mesura la màquina tant com el mètode) i per què sí que serveix el ritme de creixement del cost respecte de la mida de l'entrada. Hem definit les tres notacions —la O gran com a fita superior, Ω com a fita inferior i Θ com a fita ajustada—, hem recorregut la jerarquia d'ordres comuns des d'O(1) fins a O(2ⁿ) comprovant amb la xarxa de parades de RutaBus que la diferència entre ells no és acadèmica sinó brutal, i hem practicat les dues regles de simplificació: descartar constants i quedar-se amb el terme dominant. Amb aquest llenguatge a la mà, al Mòdul 2 aprendrem a calcular la complexitat d'un algorisme real: analitzarem codi Python línia a línia per derivar-ne la complexitat temporal (02-01), en mesurarem també el consum de memòria (02-02) i en distingirem el comportament en el millor cas, el pitjor i el mitjà (02-03) — començant, com no podia ser d'una altra manera, pels algorismes que ja hem escrit per a RutaBus.