DAA - Divide & Conquer

Molti algoritmi sono di natura ricorsiva per risolvere un dato problema ricorsivamente trattando sotto-problemi.

In divide and conquer approach, un problema viene diviso in problemi più piccoli, quindi i problemi più piccoli vengono risolti indipendentemente e infine le soluzioni di problemi più piccoli vengono combinate in una soluzione per il problema più grande.

In generale, gli algoritmi divide et impera hanno tre parti:

Divide the problem in una serie di problemi secondari che sono istanze più piccole dello stesso problema.
Conquer the sub-problemsrisolvendoli in modo ricorsivo. Se sono abbastanza piccoli, risolvi i sottoproblemi come casi base.
Combine the solutions ai sotto-problemi nella soluzione del problema originale.

Pro e contro dell'approccio Divide and Conquer

L'approccio divide et impera supporta il parallelismo poiché i problemi secondari sono indipendenti. Quindi, un algoritmo, progettato utilizzando questa tecnica, può essere eseguito sul sistema multiprocessore o su macchine diverse contemporaneamente.

In questo approccio, la maggior parte degli algoritmi sono progettati utilizzando la ricorsione, quindi la gestione della memoria è molto alta. Per le funzioni ricorsive viene utilizzato lo stack, in cui è necessario memorizzare lo stato della funzione.