El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Divideix i Venceràs

Següent ►
►

Al Mòdul 2 vam aprendre a mesurar algorismes: sabem calcular-ne el cost temporal i el consum de memòria, i distingir el millor cas del pitjor. Però mesurar no és crear. Quan l'equip de RutaBus s'enfronta a un problema nou — trobar l'hora punta d'una línia, detectar les dues parades més pròximes entre si —, necessita alguna cosa més que un cronòmetre: necessita estratègies de disseny, patrons provats per construir algorismes des de zero. Aquesta lliçó inaugura el Mòdul 3 amb la primera i potser més elegant de les quatre grans estratègies que vam anticipar a 01-02: divideix i venceràs (divide and conquer). La idea és enganyosament simple — partir el problema en trossos, resoldre cada tros i recompondre la solució — però d'aquesta idea neixen alguns dels algorismes més eficients que s'han escrit mai.

Contingut

  1. L'esquema general: dividir, conquerir, combinar
  2. Quan s'aplica (i quan no)
  3. Primer exemple RutaBus: l'hora punta d'una línia
  4. Segon exemple RutaBus: el parell de parades més properes en 1D
  5. Raonar el cost: comptar nivells de divisió
  6. Algorismes cèlebres de l'estratègia

L'esquema general: dividir, conquerir, combinar

Divideix i venceràs resol un problema de mida n mitjançant tres fases:

  1. Dividir: partir l'entrada en dos o més subproblemes del mateix tipus però de mida més petita (habitualment dues meitats).
  2. Conquerir: resoldre cada subproblema recursivament. Quan el subproblema és tan petit que la resposta és immediata (una parada, una franja horària), som al cas base — el mateix concepte que vam estudiar en veure la recursivitat a 01-02.
  3. Combinar: fusionar les solucions parcials en la solució del problema original.
flowchart TD
    A["Problema de mida n"] --> B["Dividir"]
    B --> C["Subproblema n/2"]
    B --> D["Subproblema n/2"]
    C --> E["Conquerir (recursió)"]
    D --> F["Conquerir (recursió)"]
    E --> G["Combinar"]
    F --> G
    G --> H["Solució del problema original"]

Fixa't que la recursió fa gairebé tota la feina per nosaltres: el nostre esforç de disseny es concentra a decidir com dividir i, sobretot, com combinar. La fase de combinació és on solen amagar-se tant la genialitat com els errors.

Quan s'aplica (i quan no)

No tot problema es deixa trossejar. Divideix i venceràs funciona bé quan es compleixen tres condicions:

  • Els subproblemes són del mateix tipus que l'original. Buscar el màxim en mitja llista continua sent "buscar el màxim en una llista". Si en dividir el problema canvia de naturalesa, la recursió no hi encaixa.
  • Els subproblemes són independents. Resoldre la meitat esquerra no necessita res de la meitat dreta. Aquesta condició és crucial: si els subproblemes se solapen (comparteixen feina), divideix i venceràs repeteix càlculs i es torna ineficient — aquest escenari és justament el que resoldrà la programació dinàmica a 03-03.
  • Combinar és més barat que resoldre des de zero. Si fusionar les solucions parcials costa tant com el problema sencer, no hi hem guanyat res.
Condició Si es compleix Si no es compleix
Subproblemes del mateix tipus La recursió és natural Buscar una altra estratègia
Subproblemes independents Cap feina repetida Programació dinàmica (03-03)
Combinació barata El cost total baixa El trossejat no aporta res

Primer exemple RutaBus: l'hora punta d'una línia

Comencem amb un exemple deliberadament senzill per fixar l'esquema. RutaBus registra quants passatgers pugen a la línia L1 en cada franja de 15 minuts. El servei de planificació vol conèixer l'hora punta: el màxim d'aquesta llista de recomptes.

recomptes_l1 = [12, 45, 78, 33, 91, 27, 64, 50]
# 8 franges de 15 min: de 07:00 a 09:00

Ja sabríem resoldre-ho amb un bucle O(n), com vam fer amb parada_mes_propera a 01-01. Ara ho resoldrem amb divideix i venceràs per veure l'esquema en la seva forma més pura:

def maxim_passatgers(recomptes, inici, fi):
    """Màxim de recomptes[inici..fi] (tots dos inclosos) per divideix i venceràs."""
    # CAS BASE: una sola franja -> el màxim és ella mateixa
    if inici == fi:
        return recomptes[inici]

    # DIVIDIR: partim el rang per la meitat
    mig = (inici + fi) // 2

    # CONQUERIR: màxim de cada meitat, recursivament
    max_esq = maxim_passatgers(recomptes, inici, mig)
    max_dret = maxim_passatgers(recomptes, mig + 1, fi)

    # COMBINAR: el màxim global és el més gran dels dos parcials
    return max_esq if max_esq >= max_dret else max_dret

hora_punta = maxim_passatgers(recomptes_l1, 0, len(recomptes_l1) - 1)
print(hora_punta)  # 91

Desglossem cada peça:

  • Cas base (inici == fi): un rang d'una sola franja no es pot dividir més; el seu màxim és trivial. Sense aquest cas la recursió no acabaria — recorda la propietat de finitud de Knuth (01-01).
  • Dividir: calculem mig i obtenim dos rangs, [inici..mig] i [mig+1..fi]. Observa que passem índexs en lloc de fer slices (recomptes[:mig]): a 02-01 vam veure que cada slice copia dades i costa O(k); amb índexs, la divisió és O(1).
  • Conquerir: dues crides recursives, cadascuna sobre la meitat de les franges.
  • Combinar: una única comparació, O(1).

L'execució sobre les 8 franges forma un arbre de crides:

flowchart TD
    A["[0..7] → 91"] --> B["[0..3] → 78"]
    A --> C["[4..7] → 91"]
    B --> D["[0..1] → 45"]
    B --> E["[2..3] → 78"]
    C --> F["[4..5] → 91"]
    C --> G["[6..7] → 64"]
    D --> H["12"] & I["45"]
    E --> J["78"] & K["33"]
    F --> L["91"] & M["27"]
    G --> N["64"] & O["50"]

Una confessió important: aquest algorisme fa exactament n − 1 comparacions, les mateixes que el bucle lineal. Aquí divideix i venceràs no hi guanya res en temps (i a més consumeix pila de recursió, com vam analitzar a 02-02). L'hem fet servir perquè mostra l'esquema amb total claredat. El guany real apareix quan dividir ens permet evitar feina, com en l'exemple següent.

Segon exemple RutaBus: el parell de parades més properes en 1D

A 02-01 vam escriure parells_connectables, que comparava totes les parelles de parades: O(n²). Un problema germà: l'equip d'infraestructura vol detectar les dues parades més pròximes entre si d'una avinguda (si estan massa juntes, probablement en sobra una). Ho simplifiquem a 1D: cada parada queda representada pel seu quilòmetre sobre l'avinguda.

kms = [0.3, 5.1, 1.2, 4.0, 2.8, 0.9]   # Plaça Major, Estació Nord, ...

La força bruta compararia les n(n−1)/2 parelles — la suma aritmètica que vam deduir a 02-01 —: O(n²). Divideix i venceràs ho abaixa a O(n log n):

def distancia_minima(kms_ordenats, inici, fi):
    """Distància mínima entre dues parades de kms_ordenats[inici..fi].
    Precondició: la llista està ordenada per quilòmetre."""
    # CAS BASE: amb menys de dues parades no hi ha parella possible
    if fi - inici < 1:
        return float("inf")

    # DIVIDIR
    mig = (inici + fi) // 2

    # CONQUERIR: millor parella dins de cada meitat
    millor_esq = distancia_minima(kms_ordenats, inici, mig)
    millor_dret = distancia_minima(kms_ordenats, mig + 1, fi)

    # COMBINAR: la parella guanyadora pot CREUAR la frontera.
    # Com que la llista està ordenada, l'única parella creuada candidata és
    # (última de l'esquerra, primera de la dreta).
    creuament = kms_ordenats[mig + 1] - kms_ordenats[mig]

    return min(millor_esq, millor_dret, creuament)

kms_ordenats = sorted(kms)   # [0.3, 0.9, 1.2, 2.8, 4.0, 5.1]
print(distancia_minima(kms_ordenats, 0, len(kms_ordenats) - 1))
# 0.3  -> entre les parades dels km 0.9 i 1.2

Punts clau:

  • La fase de combinar ja no és trivial: la millor parella podria tenir una parada a cada meitat. Gràcies a l'ordenació prèvia, n'hi ha prou d'examinar una parella fronterera, no totes les creuades.
  • El cas base retorna float("inf") ("infinit"): un valor neutre que mai no guanya a un min. És un patró molt habitual per dir "aquí no hi ha solució".
  • Siguem honestos: amb la llista ja ordenada, un simple recorregut de parelles adjacents també resoldria això en O(n). Fem servir la versió recursiva perquè (a) il·lustra una combinació no trivial i (b) és l'avantsala directa del problema real en 2D (parades sobre un mapa), on el recorregut lineal ja no existeix i divideix i venceràs manté exactament aquesta estructura.

Raonar el cost: comptar nivells de divisió

Com s'analitza un algorisme que es crida a si mateix dues vegades? A 02-01 vam comptar crides recursives una a una; amb divideix i venceràs hi ha un mètode més còmode: comptar nivells.

Cada nivell de recursió divideix la mida per 2: n → n/2 → n/4 → … → 1. La pregunta "quantes vegades puc dividir n entre 2 fins a arribar a 1?" té per resposta, precisament, log₂ n — la mateixa intuïció que vam associar a O(log n) en la jerarquia de 01-03.

El cost total s'estima així:

cost total ≈ (nombre de nivells) × (feina per nivell)

Feina de dividir + combinar per crida Feina per nivell Nivells Cost total
O(1) (ex.: maxim_passatgers) dominen les ~n fulles de l'arbre log₂ n O(n)
O(n) repartit al nivell (ex.: fusionar meitats ordenades) O(n) a cada nivell log₂ n O(n log n)

Dues lectures d'aquesta taula:

  • A maxim_passatgers, cada crida combina en O(1); l'arbre té uns 2n − 1 nodes en total, així que el cost és O(n). Per això no millorava el bucle: la feina la manen les fulles.
  • Quan combinar costa O(n) per nivell, tenim O(n) de feina en cadascun dels log₂ n nivells: O(n log n), la complexitat estrella dels bons algorismes d'ordenació.

Aquest segon patró s'escriu formalment com la recurrència T(n) = 2·T(n/2) + O(n): "el cost per a mida n és el de dos subproblemes de mida n/2 més una feina lineal de combinació". Resoldrem aquesta recurrència amb tot el rigor quan analitzem el merge sort a 04-03; de moment, queda't amb el mètode dels nivells, que dona la resposta correcta en els casos habituals.

Algorismes cèlebres de l'estratègia

Divideix i venceràs és la partida de naixement de diversos clàssics que estudiarem, ja amb implementació completa, al Mòdul 4:

Algorisme Com divideix Cost On el veurem
Cerca binària Descarta una meitat a cada pas (només un subproblema!) O(log n) 04-01
Merge sort Ordena cada meitat i les fusiona O(n log n) 04-03
Quick sort Particiona al voltant d'un pivot O(n log n) de mitjana 04-04
Multiplicació de Karatsuba Parteix els nombres en meitats de dígits ≈ O(n^1.585) (només menció)

No els implementarem aquí: en aquest mòdul ens interessa l'estratègia; al Mòdul 4, els clàssics que va engendrar.

Errors Comuns i Consells

  • Oblidar el cas base o definir-lo malament. Un rang buit o d'un element s'ha de tallar en sec. Prova sempre la teva funció amb n = 0, n = 1 i n = 2 abans que amb llistes grans.
  • Dividir amb slices en lloc d'índexs. llista[:mig] copia O(k) elements a cada nivell (cost ocult de 02-01) i dispara la memòria (02-02). Passa inici i fi.
  • Errors de ±1 a la frontera. Si les meitats fossin [inici..mig] i [mig..fi] (amb mig repetit), la recursió podria no reduir la mida i no acabar mai. Verifica que totes dues meitats són estrictament més petites que el rang original.
  • Ignorar les solucions que creuen la frontera. A distancia_minima, oblidar la parella fronterera produeix resultats incorrectes silenciosos. En dissenyar la combinació pregunta't sempre: "pot la solució tenir un peu a cada meitat?".
  • Aplicar l'estratègia per inèrcia. Si combinar no abarateix res (cas del màxim), un bucle simple és millor: igual de ràpid, més llegible i sense gastar pila de recursió.

Exercicis

Exercici 1

Escriu total_passatgers(recomptes, inici, fi) que sumi els passatgers d'un rang de franges usant divideix i venceràs. Identifica'n el cas base i les tres fases, i raona'n el cost total comptant nivells. Hi guanya res respecte de sum(recomptes)?

Exercici 2

RutaBus vol la franja vall (mínim de passatgers) i l'hora punta (màxim) alhora. Escriu min_i_max(recomptes, inici, fi) que retorni la tupla (minim, maxim) amb una sola passada de divideix i venceràs.

Exercici 3

A distancia_minima, per què és imprescindible que la llista estigui ordenada perquè la combinació pugui mirar una sola parella? Construeix una llista desordenada concreta amb la qual l'algorisme, aplicat sense ordenar abans, retorni un resultat incorrecte.

Solucions

Solució 1

def total_passatgers(recomptes, inici, fi):
    if inici > fi:              # cas base: rang buit
        return 0
    if inici == fi:             # cas base: una franja
        return recomptes[inici]
    mig = (inici + fi) // 2
    esq = total_passatgers(recomptes, inici, mig)      # conquerir
    dret = total_passatgers(recomptes, mig + 1, fi)
    return esq + dret                                  # combinar: O(1)

Combinar costa O(1); com a maxim_passatgers, l'arbre té ~2n nodes i el cost total és O(n). No hi guanya res davant de sum (també O(n)) i a sobre consumeix O(log n) de pila (02-02). Bon exercici d'esquema; mala idea en producció.

Solució 2

def min_i_max(recomptes, inici, fi):
    if inici == fi:
        return (recomptes[inici], recomptes[inici])
    mig = (inici + fi) // 2
    min_e, max_e = min_i_max(recomptes, inici, mig)
    min_d, max_d = min_i_max(recomptes, mig + 1, fi)
    return (min(min_e, min_d), max(max_e, max_d))

La gràcia és que cada crida retorna les dues respostes alhora i la combinació continua sent O(1); el cost total és O(n). (Dada curiosa: refinant el cas base perquè processi parelles — comparar els dos elements una vegada i decidir qui competeix pel mínim i qui pel màxim —, aquesta estructura baixa a ~1,5n comparacions davant de les ~2n de calcular mínim i màxim per separat.)

Solució 3

La combinació només mira la parella (kms[mig], kms[mig+1]) perquè, amb la llista ordenada, qualsevol altra parella creuada està més separada: els elements de l'esquerra són tots ≤ kms[mig] i els de la dreta tots ≥ kms[mig+1]. Sense ordre, aquesta garantia desapareix. Contraexemple: [0.3, 5.1, 0.4, 9.0]. Les meitats donen 4.8 (esquerra: |5.1−0.3|) i 8.6 (dreta: |9.0−0.4|), i la parella fronterera és |0.4−5.1| = 4.7. L'algorisme retornaria 4.7, però la resposta real és |0.4−0.3| = 0.1 — una parella creuada que la frontera no veu.

Conclusió

Divideix i venceràs ens ha donat el nostre primer motlle de disseny: dividir el problema en subproblemes independents del mateix tipus, conquerir-los recursivament des d'un cas base sòlid i combinar les seves respostes — la fase on viu la veritable dificultat. Hem après a estimar-ne el cost comptant nivells (log₂ n divisions) i hem comprovat, amb l'hora punta de la L1, que l'estratègia només compensa quan dividir estalvia feina, com en el parell de parades més properes (de O(n²) a O(n log n)). Els fruits més famosos del motlle — cerca binària, merge sort, quick sort — ens esperen al Mòdul 4. Però abans cal conèixer la resta de la família. Divideix i venceràs resol tots els subproblemes i després decideix; l'estratègia següent és molt més impacient: pren a cada pas la decisió que ara mateix sembla millor i mai no torna enrere. De vegades aquesta audàcia produeix algorismes òptims i rapidíssims; d'altres, desastres silenciosos. Són els algorismes greedy, i aprendre a distingir quan funcionen és l'objectiu de la propera lliçó.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats