Cosa sono gli algoritmi divide et impera?
Divide et impera è un paradigma algoritmico, simile al metodo Greedy o alla programmazione dinamica. Un tipico algoritmo divide et impera risolve problemi usando i tre step seguenti.
- Divide: suddivisione del problema dato in sotto-problemi dello stesso tipo. I sotto-problemi dovrebbero essere parte del problema originario. Questo passaggio avviene con un approccio ricorsivo, dividendo il problema finché non è possibile una suddivisione ulteriore dei sotto-problemi. In questo stadio, i sotto-problemi non sono ulteriormente scindibili ma rappresentano ancora una parte del problema reale.
- Impera: risoluzione ricorsiva dei sotto-problemi. Questo passaggio richiede di risolvere un numero elevato di sotto-problemi. Generalmente, a questo livello, i problemi vengono considerati risolti singolarmente.
- Combina: combinazione appropriata delle risposte. Quando i sotto-problemi più piccoli sono risolti, vengono combinati ricorsivamente fino a formulare una soluzione del problema di partenza. Questo approccio algoritmico funziona ricorsivamente, e gli step impera e combina sono così vicini che appaiono come uno solo.
Questo metodo, di solito, ci permette di ridurre considerevolmente la complessità temporale.
Ad esempio, Bubble Sort ha una complessità di O(n2), mentre quicksort (un'applicazione di divide et impera) riduce la complessità temporale a O(nlog(n)). L'algoritmo di ricerca lineare ha una complessità temporale di O(n), mentre quello di ricerca binaria (un'applicazione di divide et impera) riduce la complessità temporale a O(log(n)).
Di seguito, sono elencati alcuni algoritmi standard del tipo divide et impera.
Ricerca binaria è un algoritmo di ricerca. In ogni step, l'algoritmo confronta l'elemento di input (x) con il valore al centro dell'array. Se i valori coincidono, allora l'algoritmo restituisce l'indice corrispondente. Altrimenti, se x è minore dell'elemento centrale, l'algoritmo passa al lato sinistro dell'elemento centrale. In caso contrario, passa al lato destro.
Quicksort è un algoritmo di ordinamento. L'algoritmo riordina gli elementi di un array in modo che tutti gli elementi più piccoli di un elemento, detto pivot, vengono spostati alla sinistra di quest'ultimo, e tutti quelli maggiori alla sua destra. Infine, l'algoritmo ordina ricorsivamente i sotto-array a sinistra e a destra del pivot.
Merge Sort è un altro algoritmo di ordinamento. L'algoritmo divide l'array in due metà e le ordina ricorsivamente, per poi unire le due metà ordinate. La complessità temporale è O(nLogn), che sia il caso migliore, medio o peggiore. La sua complessità può essere compresa facilmente dato che la ricorrenza è: T(n) = 2T(n/2) + n.
Coppia di punti più vicini. Il problema è trovare la coppia di punti più vicini tra un insieme di punti in un piano x-y e può essere risolto in un tempo O(n2), calcolando le distanze di ogni coppia di punti e confrontando le distanze per trovare quella minore. L'algoritmo divide et impera risolve il problema in un tempo O(nLogn).
L'algoritmo di Strassen è un efficiente algoritmo per moltiplicare matrici. Un metodo semplice per moltiplicare due matrici necessita di 3 loop annidati e di un tempo O(n3). L'algoritmo di Strassen moltiplica due matrici in un tempo O(n2.8974).
L'algoritmo di Cooley–Tukey a trasformata di Fourier veloce (FFT) è l'algoritmo FFT più comune. È un algoritmo divide et impera che opera in un tempo O(nlogn).
L'algoritmo di Karatsuba è stato il primo algoritmo di moltiplicazione asintoticamente più veloce degli algoritmi quadratici. Riduce la moltiplicazione di due numeri a n cifre al massimo a n1.585 (approssimativamente log2(3)) moltiplicazioni a una cifra. È quindi pià veloce dell'algoritmo classico, il quale richiede n2 algoritmi a una cifra.
Divide et impera vs programmazione dinamica
Entrambi i paradigmi (divide et impera e programmazione dinamica) dividono un dato problema in sotto-problemi e risolvono i sotto-problemi. Come scegliere tra i due? Divide et impera dovrebbe essere utilizzato quando gli stessi sotto-problemi non vengono valutati molte volte. Altrimenti dovrebbe essere usata la programmazione dinamica o la memoizzazione.
Ad esempio, l'algoritmo di ricerca binaria è un algoritmo divide et impera, in cui non viene mai rivalutato lo stesso sotto-problema. Invece, per calcolare l'n-esimo numero di Fibonacci, è da preferire la programmazione dinamica.