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.
Applicazione dell'approccio Divide and Conquer
Di seguito sono riportati alcuni problemi, che vengono risolti utilizzando l'approccio divide et impera.
- Trovare il massimo e il minimo di una sequenza di numeri
- La moltiplicazione della matrice di Strassen
- Unisci ordinamento
- Ricerca binaria