Benvingut al primer mòdul d'Algorismes Avançats. Abans d'optimitzar res, necessitem un llenguatge comú per parlar d'algorismes: què són exactament, què vol dir que un sigui "millor" que un altre i com expressar-ne el cost de manera precisa i independent de la màquina on s'executa. En aquesta lliçó construïm aquest llenguatge: propietats d'un algorisme, el model de còmput RAM, la notació asimptòtica (O, Ω, Θ) i el pseudocodi com a eina de comunicació.

Per donar context a tot el curs treballarem amb Rutalia, una empresa fictícia de logística urbana d'última milla. Rutalia gestiona comandes, ordena repartiments i cerca adreces milers de vegades al dia. Quan gestionava 100 comandes diàries, qualsevol programa raonable funcionava. Ara en processa prop d'un milió i, de sobte, hi ha operacions que triguen hores. Entendre per què passa això —i anticipar-ho abans d'escriure codi— és l'objectiu d'aquesta lliçó.

1. Què és un algorisme i quines propietats ha de complir
2. Correcció davant d'eficiència
3. El model de còmput RAM
4. Notació asimptòtica: O, Ω i Θ
5. Jerarquia d'ordres de creixement
6. Pseudocodi i la seva equivalència amb Python

Un algorisme és un procediment computacional ben definit que pren un o diversos valors com a entrada i produeix un o diversos valors com a sortida, mitjançant una seqüència finita de passos precisos.

Perquè un procediment mereixi anomenar-se algorisme ha de complir aquestes propietats:

• Finitud: acaba després d'un nombre finit de passos. Un procés que pot no acabar mai no és un algorisme vàlid.
• Definició precisa (no ambigüitat): cada pas està especificat sense ambigüitat. "Tria una comanda raonable" no és un pas vàlid; "tria la comanda amb l'hora límit de lliurament més baixa" sí que ho és.
• Entrada: zero o més valors donats abans de començar (per exemple, la llista de comandes del dia).
• Sortida: un o més valors relacionats amb l'entrada (per exemple, la llista de comandes ordenada per hora límit).
• Efectivitat: cada operació és prou bàsica com per poder executar-se mecànicament en temps finit.

A Rutalia, "ordenar els repartiments de la furgoneta 7 per hora límit de lliurament" és un problema; el procediment concret que el resol (per exemple, un algorisme d'ordenació) és l'algorisme; i el codi Python que l'implementa és el programa. Distingir els tres nivells és important: un mateix problema admet molts algorismes, i un mateix algorisme admet moltes implementacions.

Un algorisme s'avalua en dues dimensions independents:

Dues idees clau:

• La correcció és innegociable. Un algorisme rapidíssim que de tant en tant perd comandes no serveix de res. La correcció s'argumenta raonant sobre l'algorisme (casos base, invariants de bucle), no només provant amb exemples: les proves poden mostrar la presència d'errors, però no la seva absència.
• L'eficiència es mesura en funció de la mida de l'entrada, que anomenarem habitualment n. No ens interessa "quants mil·lisegons triga al meu portàtil", sinó com creix el cost quan n creix. Aquest creixement és el que decideix si el sistema de Rutalia sobreviu al salt de 100 comandes a 1 000 000.

Un exemple il·lustratiu. Suposem dos algorismes correctes per cercar una adreça entre n adreces registrades:

• L'algorisme A fa de l'ordre de n operacions.
• L'algorisme B fa de l'ordre de log₂ n operacions (requereix dades ordenades).

Amb n = 100, A fa ~100 operacions i B ~7: la diferència és irrellevant. Amb n = 1 000 000, A fa un milió d'operacions i B ~20. Si aquesta cerca s'executa un cop per cada comanda que entra, la diferència deixa de ser acadèmica: és la diferència entre un servidor tranquil i un de saturat. A la lliçó 01-02 aprendrem a calcular aquests costos; aquí en tenim prou de saber expressar-los.

Per comptar operacions ens cal acordar què compta com "una operació". El model estàndard és la màquina RAM (Random Access Machine), una idealització d'un ordinador real amb aquestes regles:

• Hi ha una memòria de cel·les, i accedir a qualsevol cel·la costa el mateix (temps constant), tant li fa la posició. D'aquí ve "accés aleatori".
• Les operacions elementals costen una unitat de temps cadascuna: aritmètica bàsica (+, -, *, /, mòdul), comparacions (<, ==), assignacions, lectures/escriptures d'una cel·la, i salts de control (if, crida, retorn).
• Les instruccions s'executen l'una darrere l'altra, sense paral·lelisme.
• Cada cel·la emmagatzema un nombre de mida raonable (no fem trampes ficant un fitxer sencer dins "una cel·la").

És una simplificació deliberada: ignora memòries cau, pipelines i detalls del maquinari real. A canvi, ens dona una cosa valuosíssima: les anàlisis fetes sobre el model RAM prediuen el comportament relatiu dels algorismes en qualsevol màquina real. Si en el model RAM l'algorisme B creix molt més a poc a poc que l'A, en producció també ho farà (a partir d'una certa mida d'entrada).

Precaució pràctica amb Python: algunes operacions que s'escriuen en una línia no són elementals. Per exemple:

Cadascuna d'aquestes línies amaga un cost proporcional a n. En analitzar codi Python cal "traduir" mentalment cada construcció al nombre d'operacions RAM que implica.

Comptar operacions exactes és feixuc i poc útil: de debò importa si són 3n + 7 o 5n + 2 operacions? El que importa és que totes dues creixen linealment. La notació asimptòtica captura exactament això: el comportament del cost quan n es fa gran, ignorant constants multiplicatives i termes d'ordre inferior.

Definició formal: f(n) = O(g(n)) si existeixen constants positives c i n₀ tals que f(n) ≤ c · g(n) per a tot n ≥ n₀.

Intuïció: a partir d'una certa mida, f no creix mai més de pressa que g (llevat de constant). És una promesa del tipus "com a molt, així de malament". Exemple: 3n + 7 = O(n) (n'hi ha prou de prendre c = 4 i n₀ = 7, perquè 3n + 7 ≤ 4n quan n ≥ 7). També és cert que 3n + 7 = O(n²) —la fita superior no ha de ser necessàriament ajustada—, tot i que per convenció donem la més ajustada que sapiguem demostrar.

Definició formal: f(n) = Ω(g(n)) si existeixen constants positives c i n₀ tals que f(n) ≥ c · g(n) per a tot n ≥ n₀.

Intuïció: a partir d'una certa mida, f creix almenys tan de pressa com g. És la promesa contrària: "com a mínim, això costa". Exemple: qualsevol algorisme que hagi de mirar totes les comandes almenys un cop és Ω(n): no hi ha cap implementació possible que ho abaixi d'aquí.

Definició formal: f(n) = Θ(g(n)) si f(n) = O(g(n)) i alhora f(n) = Ω(g(n)).

Intuïció: f i g creixen al mateix ritme, llevat de constants. És la caracterització exacta de l'ordre de creixement. Exemple: 3n + 7 = Θ(n).

Regles pràctiques per simplificar:

• Es descarten les constants multiplicatives: 500n = O(n).
• Domina el terme més gran: n² + 1000n + 3 = Θ(n²), perquè per a n gran el terme n² eclipsa els altres.
• Les bases dels logaritmes no importen: log₂ n i log₁₀ n difereixen en una constant, així que totes dues són Θ(log n).

Un matís habitual: en la pràctica professional gairebé tothom diu "aquest algorisme és O(n log n)" volent dir Θ(n log n). És un abús de llenguatge tolerat; en aquest curs farem servir Θ quan afirmem l'ordre exacte i O quan només fitem per dalt.

Nota important: O, Ω i Θ parlen de funcions de cost, no de "pitjor cas / millor cas". Es pot donar una fita O del millor cas o una Ω del pitjor cas. La relació entre casos (millor, pitjor, mitjà) i aquestes notacions la veurem amb calma a la lliçó 01-02.

Els ordres de creixement habituals, de creixement més lent a més ràpid:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Per fer-los tangibles, suposem una màquina que executa 10⁸ operacions elementals per segon (un ordinador modest) i vegem quant trigaria cada ordre de creixement amb els volums de Rutalia:

Tres lectures d'aquesta taula que convé interioritzar:

• Amb n petit tot funciona. Amb 100 comandes, fins i tot l'algorisme quadràtic respon en una dècima de mil·lisegon. Per això els problemes de rendiment apareixen després, quan el negoci creix. El codi de Rutalia no "es va trencar": simplement n va canviar d'escala.
• El salt d'O(n log n) a O(n²) és el precipici pràctic més comú. Ordenar un milió de repartiments: 0,2 segons. Comparar cada comanda amb cada altra per detectar duplicats de manera ingènua: gairebé 3 hores. Mateix maquinari, mateix llenguatge.
• Els ordres exponencials i factorials no s'arreglen amb maquinari. Si un algorisme O(2ⁿ) és inviable per a n = 100, comprar una màquina 1000 vegades més ràpida només permet arribar a n ≈ 110. Contra el creixement exponencial, l'única arma és un algorisme millor (o acceptar solucions aproximades, com veurem al mòdul 2).

El pseudocodi és una descripció d'un algorisme a mig camí entre el llenguatge natural i un llenguatge de programació: prou precís per no ser ambigu, prou abstracte per no distreure's amb la sintaxi. És l'idioma en què s'escriuen els llibres d'algorísmia i en què convé pensar abans de programar.

Convencions habituals i la seva traducció directa a Python:

Exemple complet. Pseudocodi per trobar la comanda amb l'hora límit més primerenca (la més urgent) d'una furgoneta:

I la seva traducció literal a Python:

Observa com cada línia del pseudocodi correspon a una construcció de Python, i com els comentaris ja apunten al recompte d'operacions (quantes vegades s'executa cada línia). El bucle visita cada comanda exactament un cop, així que el cost és proporcional a n: aquest algorisme és Θ(n). L'anàlisi sistemàtica d'aquest tipus de codi —incloent-hi bucles imbricats i casos millor/pitjor/mitjà— és el tema de la propera lliçó.

Consells per escriure bon pseudocodi:

• Anomena les variables pel seu significat (hora_limit, no x).
• Explicita les precondicions (pot estar buida, la llista?).
• No incloguis detalls irrellevants del llenguatge (gestió d'excepcions, tipus exactes), però sí tot allò que afecti la correcció o el cost.
• Si un pas amaga feina no constant ("cercar d a la llista"), sigues-ne conscient: en analitzar, aquest pas no costa 1.

• Confondre O amb "pitjor cas". O és una fita superior sobre una funció; es pot aplicar al pitjor cas, al millor o al mitjà. Dir "el millor cas d'aquest algorisme és O(n)" és perfectament legítim.
• Creure que O(1) vol dir "ràpid". Vol dir "cost que no depèn de n". Una operació O(1) pot costar 10 segons fixos; una O(n) amb una constant minúscula pot guanyar-li per a tots els n realistes. La notació asimptòtica compara creixements, no temps absoluts.
• Ignorar les constants quan n és petit. Per a llistes de 20 comandes, un algorisme O(n²) senzill pot ser més ràpid a la pràctica que un O(n log n) sofisticat. L'asimptòtica mana quan n creix; el sentit comú mana sempre.
• Oblidar el cost ocult de les operacions de Python. x in llista, llista.insert(0, x), llista[:] o un slice costen O(n), encara que càpiguen en una línia. És l'error número u en analitzar codi Python.
• Escriure pseudocodi ambigu. Si dues persones poden interpretar un pas de manera diferent, no és pseudocodi: és prosa. Reescriu-lo fins que només admeti una lectura.
• Consell: quan dubtis de l'ordre de creixement, pregunta't què passa si n es multiplica per 10. El cost es multiplica per 10 (lineal), per 100 (quadràtic) o gairebé no canvia (logarítmic)? Aquesta prova mental resol la majoria de dubtes.

Simplifica cada funció de cost a la seva notació Θ i ordena-les de menor a major creixement:

1. f₁(n) = 4n² + 100n + 7
2. f₂(n) = 50·n·log n + 3n
3. f₃(n) = 2ⁿ + n¹⁰
4. f₄(n) = 1000 (constant)
5. f₅(n) = 7n + 12·log n

El sistema de detecció de comandes duplicades de Rutalia executa exactament n²/2 operacions elementals per a n comandes, en una màquina de 10⁸ operacions per segon.

1. Quant triga amb n = 1 000, n = 100 000 i n = 1 000 000?
2. Un enginyer proposa un algorisme alternatiu de 20 · n · log₂ n operacions. Quant trigaria amb n = 1 000 000? A partir de quina escala aproximada compensa el canvi?

Tradueix a Python el pseudocodi següent, que comprova si alguna comanda de la furgoneta supera el pes màxim permès, i indica de manera raonada el seu ordre de creixement en el pitjor cas i en el millor cas.

Solució 1

1. f₁ = Θ(n²) — domina 4n²; es descarten la constant i els termes menors.
2. f₂ = Θ(n log n) — n log n domina n.
3. f₃ = Θ(2ⁿ) — qualsevol exponencial domina qualsevol polinomi, fins i tot n¹⁰.
4. f₄ = Θ(1) — no depèn de n.
5. f₅ = Θ(n) — n domina log n.

Ordre de menor a major creixement: f₄ (Θ(1)) < f₅ (Θ(n)) < f₂ (Θ(n log n)) < f₁ (Θ(n²)) < f₃ (Θ(2ⁿ)).

Solució 2

1. Amb n = 1 000: 10⁶/2 = 5·10⁵ operacions → 0,005 s. Amb n = 100 000: 10¹⁰/2 = 5·10⁹ → 50 s. Amb n = 1 000 000: 10¹²/2 = 5·10¹¹ → 5 000 s ≈ 83 minuts. Observa el patró quadràtic: multiplicar n per 10 multiplica el temps per 100.
2. Amb n = 1 000 000: log₂(10⁶) ≈ 20, per tant 20 · 10⁶ · 20 = 4·10⁸ operacions → 4 segons. Igualant n²/2 = 20·n·log₂ n s'obté n = 40·log₂ n, que es compleix al voltant de n ≈ 350. És a dir: per sota d'unes ~350 comandes l'algorisme quadràtic (amb la seva constant petita) és competitiu; a l'escala actual de Rutalia, el canvi és imprescindible. Moralitat: les constants decideixen amb n petit; l'ordre de creixement decideix amb n gran.

Solució 3

• Pitjor cas: cap comanda no supera el màxim (o només el supera l'última). El bucle recorre les n comandes → Θ(n).
• Millor cas: la primera comanda ja supera el màxim. Es fa una sola comparació → Θ(1).

Fixa't com un mateix algorisme té funcions de cost diferents segons el cas; formalitzar aquesta distinció és part de la propera lliçó. Errors comuns aquí: oblidar el return False final (la funció retornaria None), o acumular els resultats en una llista en comptes de sortir tan bon punt es troba el primer (es perdria el millor cas Θ(1)).

En aquesta lliçó hem construït el vocabulari fonamental del curs. Un algorisme és un procediment finit, precís i efectiu que transforma entrades en sortides; es jutja primer per la seva correcció i després per la seva eficiència. Per mesurar l'eficiència de manera independent de la màquina fem servir el model RAM (cada operació elemental costa 1) i la notació asimptòtica: O fita per dalt, Ω per baix i Θ caracteritza el creixement exacte. La jerarquia d'ordres —d'O(1) a O(n!)— explica per què el programari de Rutalia funcionava amb 100 comandes i s'ofega amb un milió: no és qüestió de maquinari, sinó de creixement. Finalment, el pseudocodi ens dona un idioma precís per dissenyar abans de programar, amb traducció directa a Python.

Ja sabem expressar costos; el pas següent és calcular-los. A la propera lliçó, Anàlisi de Complexitat, aprendrem les tècniques sistemàtiques per determinar la complexitat temporal i espacial d'un algorisme: recompte d'operacions, bucles imbricats i dependents, anàlisi per casos (millor, pitjor, mitjà), anàlisi amortitzada i una primera aproximació a les recurrències. Analitzarem funcions reals del codi de Rutalia i descobrirem, amb números, on s'amaga aquell procés que triga hores.