Aquest mapa explica com es calcula el cost d’un algorisme: quantes operacions fa en funció de la mida de les dades, n, i com creix quan n creix.
El cost és una funció de n. Els segons depenen de l’ordinador; les operacions, no.
Prem cada requadre per veure’n l’explicació. Les fletxes ← → (o els botons del peu) passen a la següent i Esc la tanca. Quan ja l’has vist, hi apareix un ✓; prem-lo per treure’l. Els requadres amb «?» són d’altres nivells.
Aquest mapa explica com es calcula el cost d’un algorisme: quantes operacions fa un programa. Cada requadre té una explicació curta i, en alguns casos, un exercici.
Un algorisme és més ràpid quan fa menys operacions.
Prem cada requadre per veure’n l’explicació. Les fletxes ← → passen a la següent i Esc la tanca. Quan ja l’has vist, hi apareix un ✓.
4t ESO (per a valents). Versió simplificada: regles de càlcul, ordre respecte a n i cerca dicotòmica. Sense notació O(·) formal, sense gràfiques dels algoritmes i sense el recuadre d’operacions.
Encaixa a: Digitalització 4t (pensament computacional: criteris 3.1 i 3.2, algorismes lògics i eficients).
Activitat suggerida: comptar les operacions d’un bucle i després comprovar amb la cerca dicotòmica quants passos fa.
PTD-I · 1r de Batxillerat. S’hi afegeixen les regles de càlcul (seqüència, condicional i bucle), la notació O(·), les gràfiques de creixement i de temps, la cerca lineal i l’ordenació per selecció. Els experiments de temps (ms) deixen de ser el centre: el que es mesura és el nombre d’operacions.
Encaixa a: Programació i Tractament de Dades I: CEsp1 (anàlisi i disseny d’algorismes, criteri 1.3 sobre el cost computacional) i CEsp3 (eficiència i complexitat de les operacions en estructures de dades).
Activitat suggerida: amb 10⁹ operacions per segon i n = 10⁶, calcular quant tardarien la cerca lineal (n) i la bombolla (n(n−1)/2), i comparar-ho amb la gràfica de temps.
PTD-II · 2n de Batxillerat. Mateix contingut que PTD-I: regles de càlcul, notació O(·), gràfiques de creixement i els algoritmes de cerca i ordenació.
Encaixa a: Programació i Tractament de Dades II: CEsp1 (algorismes i pensament computacional).
Activitat suggerida: comparar a mà la cerca lineal i la dicotòmica amb n = 1 000 000 i justificar la diferència.
Els recuadres amb «?» estan ocults en aquest nivell: un clic els descobreix i mostra la seva relació, un altre n’obre la finestra i, després de veure-la, un altre clic els torna a amagar. El botó 🔗 copia un enllaç amb el nivell i els recuadres descoberts.
El selector Nivell canvia el mapa i totes les finestres. A l’adreça es guarden el nivell (?edad=4eso, ptd1 o ptd2) i els recuadres descoberts (&ver=casos,fonts).
Quan diem que un algorisme és ràpid, cal dir ràpid en què. Els segons depenen de l’ordinador, del sistema i del que s’estigui executant. Per això comptem operacions.
Quan compares dos algorismes, pregunta’t: què creix i quant?
El cost computacional mesura el treball que fa un programa segons la mida de les dades (n). Mira dues coses: el temps (nombre d’operacions) i la memòria (quant espai ocupa).
El cost computacional d’un algorisme és el nombre d’operacions elementals que fa, en funció de la mida de les dades, n. Els segons depenen de l’ordinador; les operacions, no.
Una operació elemental (assignació, suma, comparació o accés a una posició) costa 1. Es compta el pitjor cas, que és el que garanteix el resultat per a qualsevol dada.
| Funció T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
Els segons no serveixen per comparar algorismes. Compta operacions i mira com creixen quan creix n.
La mida n. Totes les fórmules depenen d’una mida, n: el nombre de dades que rep l’algorisme. Defineix n abans de comptar (nombre d’elements, de dígits o de files, segons el problema).
Un programa fa instruccions una darrere l’altra. Per calcular el cost, suma les instruccions. Si hi ha un bucle, multiplica pel nombre de vegades que es repeteix.
Una instrucció simple costa 1. Un bucle multiplica el cost del seu cos pel nombre de repeticions.
Un programa combina quatre estructures. El cost total es calcula aplicant una regla a cada una.
| Estructura | Regla de cost | Exemple |
|---|---|---|
| Instrucció simple | 1 | x ← x + 1 → 1 |
| Seqüència | suma dels costos | A; després B → T(A) + T(B) |
| Condicional | test + el camí més car | si … llavors … sinó … → 1 + màxim(T₁, T₂) |
| Bucle | iteracions × cost del cos | per i de 1 a n: x ← x + 1 → n |
Quan no saps quin camí d’un condicional s’executarà, fes servir el més car: és el pitjor cas.
El cost d’un bucle és el cost del seu cos multiplicat pel nombre de repeticions. Una operació no es nota; un milió, sí.
| Estructura | Operacions amb n = 1 000 | Operacions amb n = 1 000 000 |
|---|---|---|
| Un bucle | 1 000 | 1 000 000 |
| Dos bucles niats | 1 000 000 | 1 000 000 000 000 |
Compta quantes vegades s’executa el cos més intern. Un bucle de n passos fa n operacions; dos bucles niats de n passos fan n · n.
Dos bucles niats són O(n²); un bucle, O(n).
Una estructura que sembla senzilla («només és un bucle») pot amagar una cerca dins. Mira sempre què hi ha dins del bucle.
Un bucle repeteix el seu cos. El cost total és el cost del cos multiplicat pel nombre de repeticions.
| Estructura | Operacions amb n = 1 000 | Operacions amb n = 1 000 000 |
|---|---|---|
| Un bucle | 1 000 | 1 000 000 |
| Dos bucles niats (n · n) | 1 000 000 | 1 000 000 000 000 |
| Dos bucles, el segon fins a i | 500 500 | 500 000 500 000 |
Un bucle és O(n). Dos bucles niats són O(n²). Els bucles niats que van fins a i fan n(n+1)/2 passos: també O(n²), perquè ignorem la constant ½.
Una estructura que sembla senzilla («només és un bucle») pot amagar una cerca dins. Mira sempre què hi ha dins del bucle.
La bombolla compara veïns i els intercanvia si estan en ordre incorrecte. Repeteix passades fins que no fa cap intercanvi. És l’algorisme típic per entendre el cost, perquè es pot comptar tot.
| n (dades) | Comparacions (pitjor cas) | Intercanvis (mitjana) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Cada passada situa el valor més gran al final. Amb n dades, la primera passada fa n−1 comparacions, la següent n−2, i així fins a 1. En total, en el pitjor cas: n(n−1)/2.
Fixa’t: si multipliques les dades per 10, el treball es multiplica per 100.
Això és O(n²). Les comparacions creixen com el quadrat de n.
La bombolla compara cada parella de veïns i intercanvia els que estan desordenats. Després de cada passada, el valor més gran queda al final.
| n (dades) | Comparacions (pitjor cas) | Intercanvis (mitjana) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
La primera passada fa n−1 comparacions, la segona n−2, i així fins a 1. Total en el pitjor cas: (n−1) + (n−2) + … + 1 = n(n−1)/2, és a dir O(n²).
Gràfica de temps: el temps és proporcional al nombre d’operacions. Amb 10⁹ operacions per segon, 10⁶ operacions tarden 1 ms.
Si la llista està ordenada, no cal mirar-la tota. Mires el mig i descartes la meitat que no pot contenir el que busques. Cada pas redueix la mida a la meitat.
La llista és 1, 2, 3… n: no cal guardar-la tota a memòria, per això es pot provar amb 1 000 000 000.
| n (dades) | Passos dicotòmica (pitjor cas) | Comparacions lineal (pitjor cas) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Cada pas fa una comparació i elimina la meitat. Els passos són aproximadament log₂ n. Per això 1 000 000 000 de dades només necessiten 30 passos.
Això és O(log n).
La dicotòmica només funciona si la llista està ordenada. Ordenar-la també té un cost.
La cerca dicotòmica mira el mig de la llista ordenada i descarta la meitat que no pot contenir el que busques. Cada pas divideix per 2.
La llista és 1, 2, 3… n. Només es compten els passos: no cal guardar-la a memòria.
| n (dades) | Passos (pitjor cas) | Cerca lineal (pitjor cas) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Cada pas redueix la mida a la meitat: després de k passos queden n / 2ᵏ elements. Com que n / 2ᵏ = 1 quan k = log₂ n, el cost és O(log n).
La cerca dicotòmica només funciona si la llista està ordenada. Ordenar-la també té un cost.
Gràfica de temps: el temps és proporcional al nombre d’operacions. Amb 10⁹ operacions per segon, 10⁶ operacions tarden 1 ms.
Quan les dades creixen, el cost creix a un ritme concret. La notació O(·) guarda només aquest ritme i ignora les constants.
O(log n) creix molt poc: quan n passa de 1 a 20, només arriba a ≈ 4,3, mentre que O(n) arriba a 20.
Amb n petit totes les corbes semblen properes; a partir de n ≈ 10 la quadràtica se separa de les altres.
| Funció | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1): el cost no depèn de n. O(log n): cada pas divideix per 2 (dicotòmica). O(n): proporcional a n (cerca lineal). O(n log n): típic dels bons algorismes d’ordenació. O(n²): dos bucles niats (bombolla, selecció).
Quan n es multiplica per 10: amb O(n) el cost es multiplica per 10; amb O(n²), per 100; amb O(log n), gairebé no canvia.
Ignora les constants i els termes petits: 3n² + 5n és O(n²).
L’ordre respecte a n explica com creix el cost quan creixen les dades. És la idea més important d’aquest mapa.
Quan n es multiplica per 10, un cost O(n) també es multiplica per 10, però un cost O(n²) es multiplica per 100.
Si el cost és O(n), el treball creix igual que les dades. Si és O(n²), amb el doble de dades el treball es quadrupla.
El que importa és com creix, no el nombre exacte d’operacions.
El mateix algorisme pot trigar més o menys segons les dades. Per això l’anàlisi distingeix tres casos: millor, mitjà i pitjor.
| Cas | Bombolla | Dicotòmica |
|---|---|---|
| Millor | n−1 comparacions (llista ja ordenada) | 1 pas (el mig és el buscat) |
| Mitjà | ≈ n²/2 comparacions | ≈ log₂ n passos |
| Pitjor | n(n−1)/2 comparacions | ⌊log₂ n⌋ + 1 passos |
Si el quocient és proper a 2, el creixement és aproximadament lineal; si és proper a 4, quadràtic. El soroll del navegador fa que no sigui exacte: per això es fa la mediana de 3 repeticions.
Per avaluar un algorisme cal mirar les dades de pitjor cas (les que el fan treballar més), però també el cas mitjà, que sol ser el més habitual.
Una sola mesura d’un cas concret no diu quin és el pitjor. Analitza el cas i després mesura.
La cerca lineal mira els elements un a un fins trobar el que busques. És el mètode més simple i serveix de referència per comparar amb la cerca dicotòmica.
Es compara cada element amb el valor buscat fins a trobar-lo o arribar al final.
| Cas | Comparacions | Amb n = 1 000 000 |
|---|---|---|
| Millor (és el primer) | 1 | 1 |
| Mitjà (és a la meitat) | n / 2 | 500 000 |
| Pitjor (és l’últim o no hi és) | n | 1 000 000 |
El cost és O(n): cada element s’examina com a molt una vegada.
Quan donis un cost, digues quin cas és: el millor, el mitjà o el pitjor.
Gràfica de temps: el temps és proporcional al nombre d’operacions. Amb 10⁹ operacions per segon, 10⁶ operacions tarden 1 ms.
L’ordenació per selecció busca el mínim de la part no ordenada i el posa al davant. Repeteix-ho fins que tota la llista està ordenada.
La primera passada busca el mínim entre n elements (n−1 comparacions) i el posa a la primera posició. La següent busca entre n−1 elements, i així fins a l’últim.
| n (dades) | Comparacions (sempre) |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
Total: (n−1) + (n−2) + … + 1 = n(n−1)/2, és a dir O(n²) en tots els casos. Fa com a molt n−1 intercanvis.
La selecció fa sempre les mateixes comparacions; la bombolla pot aturar-se abans si la llista ja està ordenada.
Gràfica de temps: el temps és proporcional al nombre d’operacions. Amb 10⁹ operacions per segon, 10⁶ operacions tarden 1 ms.
L’ordenació per inserció agafa cada element i el col·loca al lloc que li toca dins de la part ja ordenada.
En el pitjor cas (llista invertida) fa n(n−1)/2 comparacions: O(n²). En el millor cas (llista ja ordenada) només en fa n−1: O(n).
La inserció és ràpida quan la llista ja està quasi ordenada.
L’ordenació per fusió parteix la llista per la meitat, ordena cada meitat i després les uneix.
Cada nivell de divisions fa n passos i hi ha log₂ n nivells. El cost és O(n log n) en tots els casos.
Per a llistes grans és molt més ràpida que la bombolla.
Mesurar és fàcil de fer malament. Aquests són els errors més habituals, i com evitar-los.
Abans de dir que un algorisme és més ràpid, pregunta’t: amb quines dades, en quina màquina i quantes vegades l’he mesurat?
Llegeix cada situació i tria quin concepte explica el cas. Si en tries un que també hi és, però que no és el principal, t’ho direm.
Un programa suma 1 000 000 de nombres dins d’un bucle. Quin concepte explica per què el cost és alt?
Un programa suma 1 000 000 de nombres dins d’un bucle. Quin concepte explica per què el cost és alt?
Busques el número 42 en una llista ordenada d’un milió de números. Mires el mig, descartes la meitat i, en uns 20 passos, el trobes. Quin algorisme és?
Un algorisme recorre la llista comparant veïns i intercanviant-los. Amb la llista invertida fa n(n−1)/2 comparacions. Quin algorisme és?
Un algorisme triga 4 vegades més quan dupliques les dades. Quin concepte descriu com creix el seu cost?
Busques un número en una llista desordenada de n elements i el compares amb cada element fins trobar-lo. Quin algorisme és?
Un algorisme busca el mínim de la part no ordenada i el porta al davant. Fa n(n−1)/2 comparacions encara que la llista ja estigui ordenada. Quin algorisme és?
Aquest mapa reuneix conceptes clàssics de l’anàlisi d’algorismes i els objectius del currículum de les Illes Balears. Aquí tens on comprovar-ho i aprofundir-hi.