Algoritmo dividi e conquista
Un paradigma algoritmico molto popolare, un tipico algoritmo dividi e conquista risolve un problema usando i seguenti tre passi:
- Dividi: Rompere il problema dato in sottoproblemi dello stesso tipo.
- Conquistare: Risolvere ricorsivamente questi sottoproblemi
- Combina: Combina opportunamente le risposte
Seguono alcuni algoritmi standard che sono algoritmi Divide et Conquer:
1 – La ricerca binaria è un algoritmo di ricerca. In ogni passo, l’algoritmo confronta l’elemento di input x con il valore dell’elemento centrale dell’array. Se i valori corrispondono, restituisce l’indice di mezzo. Altrimenti, se x è inferiore all’elemento centrale, allora l’algoritmo ricorre per il lato sinistro dell’elemento centrale, altrimenti ricorre per il lato destro dell’elemento centrale.
2 – Quicksort è un algoritmo di ordinamento. L’algoritmo sceglie un elemento pivot, riordina gli elementi dell’array in modo tale che tutti gli elementi più piccoli dell’elemento pivot scelto si spostino sul lato sinistro del pivot, e tutti gli elementi più grandi si spostino sul lato destro. Infine, l’algoritmo ordina ricorsivamente i subarray a sinistra e a destra dell’elemento pivot.
3 – Merge Sort è anche un algoritmo di ordinamento. L’algoritmo divide l’array in due metà, le ordina ricorsivamente e infine fonde le due metà ordinate.
4 – Coppia di punti più vicina: Il problema è trovare la coppia di punti più vicina in un insieme di punti nel piano x-y. Il problema può essere risolto in tempo O(n²) calcolando le distanze di ogni coppia di punti e confrontando le distanze per trovare il minimo. L’algoritmo Divide and Conquer risolve il problema in tempo O(nLogn).
5 – L’algoritmo di Strassen è un algoritmo efficiente per moltiplicare due matrici. Un metodo semplice per moltiplicare due matrici ha bisogno di 3 loop annidati ed è O(n³). L’algoritmo di Strassen moltiplica due matrici in tempo O(n².8974).
6 – L’algoritmo Cooley-Tukey Fast Fourier Transform (FFT) è l’algoritmo più comune per FFT. È un algoritmo divide et impera che funziona in tempo O(nlogn).
7 – Algoritmo Karatsuba per la moltiplicazione veloce: Fa la moltiplicazione di due numeri di n cifre al massimo in 3n^(log 3) moltiplicazioni a una cifra in generale (ed esattamente n^(log3) quando n è una potenza di 2). È quindi più veloce dell’algoritmo classico, che richiede n² prodotti a una cifra.
Problema delle inversioni di conteggio
Prenderemo in considerazione un problema che si presenta nell’analisi delle classifiche, che stanno diventando importanti per una serie di applicazioni attuali. Per esempio, un certo numero di siti sul Web fanno uso di una tecnica nota come filtraggio collaborativo, in cui cercano di abbinare le vostre preferenze (per libri, film, ristoranti) con quelle di altre persone su Internet. Una volta che il sito web ha identificato le persone con gusti “simili” ai tuoi – sulla base di un confronto di come tu e loro valutate varie cose – può raccomandare nuove cose che queste altre persone hanno apprezzato. Un’altra applicazione si presenta negli strumenti di ricerca sul Web, che eseguono la stessa query su molti motori di ricerca diversi e poi cercano di sintetizzare i risultati cercando somiglianze e differenze tra le varie classifiche che i motori di ricerca restituiscono.
Un problema centrale in applicazioni come questa è il problema di confrontare due classifiche. Voi classificate un insieme di film rt, e poi un sistema di filtraggio collaborativo consulta il suo database per cercare altre persone che hanno classifiche “simili”. Ma qual è un buon modo per misurare, numericamente, quanto sono simili le classifiche di due persone? Chiaramente una classifica identica è molto simile, e una classifica completamente invertita è molto diversa; vogliamo qualcosa che interpoli la regione di mezzo.
Consideriamo di confrontare la vostra classifica e quella di uno sconosciuto dello stesso set di n film. Un metodo naturale sarebbe quello di etichettare i film da 1 a n secondo la vostra classifica, poi ordinare queste etichette secondo la classifica dello sconosciuto, e vedere quante coppie sono “fuori ordine”. Più concretamente, considereremo il seguente problema. Ci viene data una sequenza di n numeri a1, …, an; assumeremo che tutti i numeri siano distinti. Vogliamo definire una misura che ci dica quanto questa lista è lontana dall’essere in ordine crescente; il valore della misura dovrebbe essere 0 se a1 < a2 << an, e dovrebbe aumentare man mano che i numeri diventano più confusi.
Un modo naturale per quantificare questa nozione è contare il numero di inversioni. Diciamo che due indici i < j formano un’inversione se ai > aj, cioè se i due elementi ai e aj sono “fuori ordine”. Cercheremo di determinare il numero di inversioni nella sequenza a1, …, an.