TechCodeview

Divide and Conquer è un modello algoritmico. Nei metodi algoritmici, la progettazione consiste nel prendere una disputa su un input enorme, suddividere l'input in parti minori, decidere il problema su ciascuna delle parti più piccole e quindi unire le soluzioni a pezzi in una soluzione globale. Questo meccanismo per risolvere il problema è chiamato strategia Divide & Conquer.

L'algoritmo Divide and Conquer consiste in una disputa che utilizza i seguenti tre passaggi.

Dividereil problema originale in un insieme di sottoproblemi.Conquistare:Risolvi ogni sottoproblema individualmente, ricorsivamente.Combina:Metti insieme le soluzioni dei sottoproblemi per ottenere la soluzione dell’intero problema.

In generale, possiamo seguire il dividere e conquistare approccio in un processo in tre fasi.

Esempi: Gli algoritmi informatici specifici si basano sull'approccio Divide & Conquer:

1. Problema di massimo e minimo
2. Ricerca binaria
3. Ordinamento (unione ordinamento, ordinamento rapido)
4. Torre di Hanoi.

Fondamenti della strategia Divide & Conquer:

Ci sono due fondamentali nella strategia Divide & Conquer:

1. Formula relazionale
2. Condizione di arresto

1. Formula relazionale: È la formula che generiamo dalla tecnica data. Dopo la generazione della formula applichiamo la strategia D&C, ovvero risolviamo il problema in modo ricorsivo e risolviamo i sottoproblemi risolti.

2. Condizione di arresto: Quando risolviamo il problema utilizzando la strategia Divide & Conquer, allora dobbiamo sapere per quanto tempo dobbiamo applicare la strategia Divide & Conquer. Quindi la condizione in cui è necessario interrompere i nostri passaggi di ricorsione di D&C è chiamata condizione di arresto.

Applicazioni dell’approccio “Dividi e Impera”:

I seguenti algoritmi si basano sul concetto della tecnica divide et impera:

Ricerca binaria:L'algoritmo di ricerca binaria è un algoritmo di ricerca, chiamato anche ricerca a semiintervallo o ricerca logaritmica. Funziona confrontando il valore target con l'elemento centrale esistente in un array ordinato. Dopo aver effettuato il confronto, se il valore è diverso, verrà eventualmente eliminata la metà che non può contenere il target, per poi continuare la ricerca sull'altra metà. Considereremo nuovamente l'elemento centrale e lo confronteremo con il valore target. Il processo continua a ripetersi finché non viene raggiunto il valore target. Se al termine della ricerca l'altra metà risulta vuota, si può concludere che la destinazione non è presente nell'array.Ordinamento rapido:È l'algoritmo di ordinamento più efficiente, noto anche come ordinamento a scambio di partizioni. Si inizia selezionando un valore pivot da un array seguito dalla divisione del resto degli elementi dell'array in due sottoarray. La partizione viene effettuata confrontando ciascuno degli elementi con il valore pivot. Confronta se l'elemento ha un valore maggiore o minore rispetto al pivot e quindi ordina gli array in modo ricorsivo.Unisci ordinamento:È un algoritmo di ordinamento che ordina un array effettuando confronti. Inizia dividendo un array in sottoarray e quindi ordina ricorsivamente ciascuno di essi. Una volta terminato l'ordinamento, li unisce nuovamente.Coppia di punti più vicina:È un problema di geometria computazionale. Questo algoritmo enfatizza la ricerca della coppia di punti più vicina in uno spazio metrico, dati n punti, in modo tale che la distanza tra la coppia di punti sia minima.Algoritmo di Strassen:È un algoritmo per la moltiplicazione di matrici, che prende il nome da Volker Strassen. Ha dimostrato di essere molto più veloce dell'algoritmo tradizionale quando lavora su matrici di grandi dimensioni.Algoritmo di trasformata veloce di Fourier (FFT) di Cooley-Tukey:L'algoritmo della trasformata veloce di Fourier prende il nome da J. W. Cooley e John Turkey. Segue l'approccio Divide and Conquer e impone una complessità di O(nlogn).Algoritmo Karatsuba per la moltiplicazione veloce:È uno degli algoritmi di moltiplicazione più veloci del tempo tradizionale, inventato da Anatoly Karatsuba alla fine del 1960 e pubblicato nel 1962. Moltiplica due numeri di n cifre in questo modo riducendoli al massimo a una cifra.

I vantaggi del divide et impera

• Dividi e conquista tendono a risolvere con successo uno dei problemi più grandi, come la Torre di Hanoi, un puzzle matematico. È difficile risolvere problemi complicati per i quali non si ha un'idea di base, ma con l'aiuto dell'approccio divide et impera, lo sforzo è diminuito poiché si lavora sulla divisione del problema principale in due metà e quindi risolvendole in modo ricorsivo. Questo algoritmo è molto più veloce di altri algoritmi.
• Utilizza in modo efficiente la memoria cache senza occupare molto spazio perché risolve semplici sottoproblemi all'interno della memoria cache invece di accedere alla memoria principale più lenta.
• È più efficace di quella della sua controparte tecnica Brute Force.
• Poiché questi algoritmi inibiscono il parallelismo, esso non comporta alcuna modifica e viene gestito da sistemi che incorporano l'elaborazione parallela.

Svantaggi di Divide and Conquer

• Poiché la maggior parte dei suoi algoritmi sono progettati incorporando la ricorsione, è necessaria un'elevata gestione della memoria.
• Uno stack esplicito potrebbe utilizzare eccessivamente lo spazio.
• Potrebbe addirittura mandarsi in crash il sistema se la ricorsione viene eseguita rigorosamente su una quantità maggiore dello stack presente nella CPU.