Divide and Conquer
Divide and Conquer (Dividi e conquista) è una tecnica molto diffusa per risolvere problemi algoritmici. Abbiamo già visto alcuni metodi per affrontare i problemi di questo tipo: l’approccio greedy sceglie la soluzione locale più vantaggiosa in ogni passaggio, mentre la programmazione dinamica costruisce lo stato attuale basandosi sui precedenti. Nel caso di Divide and Conquer, invece, suddividiamo il problema in sottoproblemi più piccoli, li risolviamo uno alla volta e infine combiniamo i risultati per risolvere il problema iniziale. In altre parole, “dividiamo” il problema e lo “conquistiamo” unendo le soluzioni dei sottoproblemi.
Challenge
Immagina di avere 512 numeri e di disporre di 512 computer specializzati (macchine molto piccole e specializzate) che possono solo calcolare e restituire il massimo tra due numeri.
L’obiettivo è trovare il massimo tra questi 512 numeri nel minor tempo possibile.
Ogni computer può ricevere due numeri e restituire il massimo tra questi due in 1 secondo (sì, sono piuttosto lenti 🐌). Riesci a pensare a un algoritmo che permetta di calcolare il massimo di tutti i numeri nel minor tempo possibile?