In questo tutorial imparerai come funziona l'algoritmo divide et impera. Confronteremo anche l'approccio divide et impera con altri approcci per risolvere un problema ricorsivo.
Un algoritmo divide et impera è una strategia per risolvere un grosso problema
- suddividendo il problema in sotto-problemi più piccoli
- risolvere i problemi secondari e
- combinandoli per ottenere l'output desiderato.
Per utilizzare l'algoritmo di divisione e conquista, viene utilizzata la ricorsione . Informazioni sulla ricorsione in diversi linguaggi di programmazione:
- Ricorsione in Java
- Ricorsione in Python
- Ricorsione in C ++
Come funzionano gli algoritmi di divisione e conquista?
Ecco i passaggi coinvolti:
- Dividi : dividi il problema dato in sotto-problemi usando la ricorsione.
- Conquista : risolvi i problemi secondari più piccoli in modo ricorsivo. Se il problema secondario è abbastanza piccolo, risolverlo direttamente.
- Combina: combina le soluzioni dei sottoproblemi che fanno parte del processo ricorsivo per risolvere il problema reale.
Cerchiamo di capire questo concetto con l'aiuto di un esempio.
Qui, ordineremo un array usando l'approccio divide et impera (cioè merge sort).
- Sia l'array dato:
Array for merge sort - Dividi la matrice in due metà.
Dividi l'array in due sottoparti
Ancora una volta, dividi ricorsivamente ogni sottoparte in due metà finché non ottieni i singoli elementi.
Dividi l'array in sottoparti più piccole - Ora, combina i singoli elementi in modo ordinato. Qui, conquista e combina i passaggi che vanno fianco a fianco.
Combina le sottoparti
Complessità temporale
La complessità dell'algoritmo divide et impera viene calcolata utilizzando il teorema principale.
T (n) = aT (n / b) + f (n), dove, n = dimensione dell'input a = numero di sottoproblemi nella ricorsione n / b = dimensione di ogni sottoproblema. Si presume che tutti i sottoproblemi abbiano la stessa dimensione. f (n) = costo del lavoro svolto al di fuori della chiamata ricorsiva, che include il costo della divisione del problema e il costo della fusione delle soluzioni
Facciamo un esempio per trovare la complessità temporale di un problema ricorsivo.
Per un ordinamento di tipo merge, l'equazione può essere scritta come:
T (n) = aT (n / b) + f (n) = 2T (n / 2) + O (n) Dove, a = 2 (ogni volta, un problema è diviso in 2 sottoproblemi) n / b = n / 2 (la dimensione di ogni sottoproblema è la metà dell'input) f (n) = tempo impiegato per dividere il problema e fondere i sottoproblemi T (n / 2) = O (n log n) (Per capire questo, fare riferimento a il teorema maestro.) Ora, T (n) = 2T (n log n) + O (n) ≈ O (n log n)
Divide and Conquer Vs approccio dinamico
L'approccio divide et impera divide un problema in sottoproblemi più piccoli; questi sottoproblemi vengono ulteriormente risolti in modo ricorsivo. Il risultato di ogni sottoproblema non viene memorizzato per riferimento futuro, mentre, in un approccio dinamico, il risultato di ogni sottoproblema viene memorizzato per riferimento futuro.
Usa l'approccio divide et impera quando lo stesso sottoproblema non viene risolto più volte. Utilizzare l'approccio dinamico quando il risultato di un sottoproblema deve essere utilizzato più volte in futuro.
Cerchiamo di capirlo con un esempio. Supponiamo di provare a trovare la serie di Fibonacci. Poi,
Approccio Divide and Conquer:
fib (n) Se n <2, restituisce 1 Altrimenti, restituisce f (n - 1) + f (n -2)
Approccio dinamico:
mem = () fib (n) If n in mem: return mem (n) else, If n <2, f = 1 else, f = f (n - 1) + f (n -2) mem (n) = f ritorno f
In un approccio dinamico, mem memorizza il risultato di ogni sottoproblema.
Vantaggi dell'algoritmo Divide and Conquer
- La complessità per la moltiplicazione di due matrici usando il metodo ingenuo è O (n 3 ), mentre usando l'approccio divide et impera (cioè la moltiplicazione di matrici di Strassen) è O (n 2.8074 ). Questo approccio semplifica anche altri problemi, come la Torre di Hanoi.
- Questo approccio è adatto per sistemi multiprocessing.
- Fa un uso efficiente delle cache di memoria.
Dividi e conquista le applicazioni
- Ricerca binaria
- Unisci ordinamento
- Ordinamento rapido
- La moltiplicazione della matrice di Strassen
- Algoritmo di Karatsuba
