---

---

Has seguit mai una recepta de cuina? Primer talles la ceba, després sofregeixes, finalment emplates. Doncs això mateix és un algorisme, però aplicat al món de la informàtica. Els algorismes són el cor de qualsevol programa, el cervell que decideix com es fan les coses pas a pas. I creieu-me, entendre’ls és el que separa els programadors que simplement escriuen codi dels que realment resolen problemes. Acompanya’m en aquest viatge pel fascinant món dels algorismes!

Què és un Algorisme? Definició Senzilla

Si anem a la definició formal, un algorisme és un conjunt ordenat i finit d’operacions que permet trobar la solució a un problema. Traduït al català de cada dia: és una seqüència de passos clars i precisos per aconseguir un objectiu.

Algorisme vs. Programa: No són el mateix!

Aquí ve una distinció important. L’algorisme és la idea, el pla. El programa és la implementació d’aquest pla en un llenguatge concret (Python, Java, C++). És com si l’algorisme fos el plànol d’una casa i el programa, la casa construïda amb maons i ciment.

Característiques Fonamentals dels Algorismes

Un bon algorisme ha de complir tres coses:

1. Precís: Cada pas ha d’estar definit sense ambigüitats. No val dir «afegeix una mica de sucre». Has de dir «afegeix 200 grams de sucre».
2. Finit: Ha de tenir un nombre determinat de passos. No pot ser un bucle infinit que no s’acabi mai.
3. General: Ha de funcionar per a un conjunt d’entrades, no només per a un cas concret. Un algorisme per ordenar llibres ha de servir per a qualsevol llista de llibres, no només per a la teua prestatgeria.

Bondat d’un Algorisme: Com Saber si és Bo?

Per a un mateix problema, pots tenir mil algorismes diferents. Com tries el millor? Mesurant la seua bondat. I això es fa amb dos paràmetres:

• El temps que tarda a executar-se.
• Els recursos que consumeix (memòria, CPU, etc.).

Recursivitat: Quan un Algorisme es Crida a si Mateix

La recursivitat és una tècnica fascinant. Un algorisme és recursiu quan, per resoldre un problema, es crida a si mateix amb una versió més petita del mateix problema. És com les nines russes: cada nina conté una altra nina més petita dins seu.

Per exemple, per calcular el factorial d’un nombre (5! = 5 × 4 × 3 × 2 × 1), pots dir: «factorial(5) = 5 × factorial(4)». I factorial(4) tornarà a cridar-se, i així fins a arribar a factorial(1), que és el cas base que atura les crides.

Optimització: Fent que les Coses Vagin Més Ràpid

L’optimització consisteix a modificar un algorisme perquè sigui més eficient: que tardi menys o que consumeixi menys memòria. Però compte! Com deia un savi: «L’optimització prematura és l’arrel de tots els mals». Primer fes que funcioni, després fes que vagi ràpid.

Complexitat Algorísmica: Quant Tarda i Quant Consumeix?

La complexitat és la manera que tenim de mesurar l’eficiència d’un algorisme. I ho fem en funció de la mida de l’entrada (n).

Complexitat Espacial (Memòria)

És la quantitat de memòria que necessita l’algorisme per executar-se. Un algorisme que guarda mil números en un array necessitarà més memòria que un que els processa un a un.

Complexitat Temporal (Temps d’Execució)

És el temps de còmput necessari. No el mesurem en segons (que dependran de l’ordinador), sinó en nombre d’operacions que realitza l’algorisme en funció de n.

Casos d’Ús: Millor, Pitjor i Promig

El comportament d’un algorisme pot canviar dràsticament segons les dades d’entrada.

Cas Millor

És la situació més favorable. Per exemple, en un algorisme de cerca, que l’element que busques sigui el primer de la llista.

Cas Pitjor

La situació més desfavorable. En el mateix algorisme de cerca, que l’element sigui l’últim o que no hi sigui. Aquest és el cas que més ens interessa, perquè ens dona garanties: sabem que l’algorisme no tardarà mai més que això.

Cas Promig

Una mitjana de tots els casos possibles. És útil per tenir una visió realista del rendiment en situacions normals, però és més difícil de calcular.

Ordres de Complexitat (Notació Big O)

Per simplificar, fem servir la notació Big O. Descriu com creix el temps d’execució en relació amb l’entrada n.

• O(1) – Constant: L’algorisme sempre tarda el mateix, independentment de n. Accedir a un element d’un array per la seua posició. Súper ràpid.
• O(log n) – Logarítmic: El temps creix molt lentament. Cada pas redueix dràsticament la feina. La cerca binària en un array ordenat és l’exemple perfecte.
• O(n) – Lineal: El temps és proporcional a n. Si n es duplica, el temps també. Recórrer tots els elements d’una llista (cerca seqüencial).
• O(n log n) – Quasi Lineal: És el dels bons algorismes d’ordenació, com MergeSort o Quicksort (en el cas promig).
• O(n²) – Quadràtic: El temps es dispara. Si n es duplica, el temps es multiplica per 4. Algorismes d’ordenació senzills com el de la bombolla.
• O(2ⁿ) – Exponencial: Inviable per a valors grans de n. Apareix en problemes molt complexos, com trencar una contrasenya provant totes les combinacions.

Classificació dels Algorismes

Hi ha moltes maneres de classificar algorismes. Nosaltres ens centrarem en els més importants.

Algorismes d’Ordenació

Serveixen per ordenar un conjunt de dades. N’hi ha de dos tipus principals:

• Ordenació Iterativa (Bombolla, Selecció, Inserció): Utilitzen bucles (for, while). Són senzills d’entendre però ineficients per a grans volums de dades (O(n²)). L’algorisme de la bombolla compara parells d’elements adjacents i els intercanvia si estan en l’ordre incorrecte, fent «pujar» els elements més grans com si fossin bombolles.
• Ordenació Recursiva (Quicksort, Mergesort): Són molt més eficients (O(n log n)). Utilitzen la tècnica de «divideix i venceràs».
  • Quicksort: Tria un element com a pivot i divideix la llista en dos: els més petits que el pivot i els més grans. Després, ordena cada subllista recursivament.
  • MergeSort: Divideix la llista per la meitat una i altra vegada fins a tenir elements solts, i després els fusiona (merge) ordenadament.

Algorismes de Cerca

Busquen un element dins d’un conjunt de dades.

• Cerca Seqüencial: Revisa un per un tots els elements fins a trobar-lo. És senzilla però lenta (O(n)).
• Cerca Binària: Només funciona si les dades estan ordenades. Compara l’element amb el del mig, i si no és, descarta la meitat on no pot estar. És molt ràpida (O(log n)).
• Taules Hash: Utilitzen una funció (funció hash) que, a partir de l’element, calcula directament la posició on hauria de ser. És la cerca més ràpida (O(1) en el millor dels casos), però pot haver-hi col·lisions (dos elements van a la mateixa posició).

Algorismes Voraces (Greedy)

Són aquells que, en cada pas, prenen la decisió que sembla òptima en eixe moment, esperant que això porte a una solució òptima global. No sempre funcionen, però quan ho fan, són molt eficients. Un exemple clàssic és l’algorisme de Dijkstra per trobar el camí més curt entre dos punts d’un mapa.

Representació d’Algorismes

Abans de programar, és útil representar l’algorisme d’alguna manera.

• Pseudocodi: Una barreja entre llenguatge humà i estructura de programació. És fàcil d’escriure i d’entendre, i després es tradueix a qualsevol llenguatge.textPROGRAMA Sumar ENTORN: a, b, suma <- 0 ALGORISME: LLEGIR a, b suma <- a + b ESCRIURE suma FI PROGRAMA
• Diagrames de Flux: Representació gràfica amb símbols (fletxes, rombes per a decisions, rectangles per a accions). Són molt visuals i ajuden a entendre el flux de l’algorisme.
• Diagrames de Nassi-Shneiderman: També anomenats diagrames de Chapin. Són una alternativa estructurada als diagrames de flux, on les estructures de control es representen amb àrees rectangulars niades.

Conclusió

Els algorismes són molt més que una assignatura avorrida de la facultat. Són la manera com ensenyem als ordinadors a pensar i a resoldre problemes. Des de l’senzill algorisme de la bombolla fins al complex Quicksort, tots tenen el seu lloc i la seua utilitat. La propera vegada que facis una cerca a Google o utilitzis el GPS per anar a casa, recorda que darrere hi ha un algorisme treballant per a tu. I tu, quin algorisme fas servir cada dia sense saber-ho?

Preguntes Freqüents (FAQ)

1. Quin és l’algorisme d’ordenació més ràpid?
No hi ha un «més ràpid» absolut per a tots els casos. Per a ús general, Quicksort sol ser molt ràpid en la pràctica. MergeSort garanteix O(n log n) fins i tot en el pitjor cas (cosa que Quicksort no fa). I per a dades molt xicotetes, algorismes senzills com Inserció poden ser més ràpids per la seua simplicitat.

2. Què és una funció hash i per què és important?
Una funció hash és una funció que transforma qualsevol dada (un text, un fitxer) en un codi de longitud fixa, generalment un número. És important per a la cerca ràpida (taules hash), per a la integritat de dades (detectar si un fitxer ha canviat), i per a la seguretat (emmagatzemar contrasenyes de manera segura).

3. Puc programar qualsevol algorisme recursiu de manera iterativa?
Sí! Tot algorisme recursiu pot ser implementat de manera iterativa, i viceversa. La recursivitat sol ser més elegant i fàcil d’entendre per a problemes que tenen naturalesa recursiva (com recórrer arbres). La iteració sol ser més eficient en memòria perquè no ha de gestionar la pila de crides.

4. Què vol dir que un algorisme és «NP-complet»?
Sense complicar massa: és una classe de problemes per als quals no es coneix cap algorisme eficient (temps polinòmic) per resoldre’ls. Si en trobes un per a qualsevol problema NP-complet, hauràs resolt un dels problemes del mil·lenni i guanyaràs un premi d’un milió de dòlars. Exemples: el problema del viatjant (trobar la ruta més curta que passi per totes les ciutats) o el sudoku.

5. Com puc millorar en el disseny d’algorismes?
Practicant! Plataformes com LeetCode, HackerRank o CodiForce estan plenes de problemes per resoldre. També ajuda molt estudiar els algorismes clàssics (cerca, ordenació, grafs) i entendre’n la lògica, no només memoritzar el codi. I sobretot, pensa en la complexitat: després de resoldre un problema, pregunta’t: «Ho puc fer millor?».