Algoritmi Divide and Conquer - Perché non dividere in più parti di due?

It does make sense to me that this makes it faster to solve a problem if the two halves takes less than half the work of dealing with the whole data set.

Questo è non l'essenza degli algoritmi divide et impera. Di solito il punto è che gli algoritmi non possono "gestire l'intero set di dati". Invece, è diviso in pezzi che sono banali da risolvere (come l'ordinamento di due numeri), quindi quelli sono risolti banalmente e i risultati ricombinati in un modo che produce una soluzione per l'intero set di dati.

But why not split the data set in three parts? Four? n?

Principalmente perché suddividerlo in più di due parti e ricombinare più di due risultati risulta in un'implementazione più complessa ma non modifica la caratteristica fondamentale (Big O) dell'algoritmo - la differenza è un fattore costante e può comportare un rallentamento se la divisione e la ricombinazione di più di 2 sottositi creano un sovraccarico aggiuntivo. / p>

Ad esempio, se esegui un ordinamento di unione a 3 vie, nella fase di ricombinazione ora devi trovare il massimo di 3 elementi per ogni elemento, che richiede 2 confronti invece di 1, quindi dovrai fare il doppio molti confronti in generale. In cambio, riduci la profondità di ricorsione di un fattore di ln (2) / ln (3) == 0,63, quindi hai il 37% di swap in meno, ma 2 * 0,63 == 26% di confronti in più (e accessi alla memoria). Che sia buono o cattivo dipende da quale è più costoso nel tuo hardware.

I have also seen many references to 3-way quicksort. When is this faster?

A quanto pare una variante dual pivot di quicksort può essere dimostrata richiedono lo stesso numero di confronti ma in media il 20% di swap in meno, quindi è un guadagno netto.

What is used in practice?

In questi giorni quasi nessuno programma più i propri algoritmi di ordinamento; ne usano uno fornito da una biblioteca. Ad esempio, la API Java 7 utilizza effettivamente il quicksort dual-pivot.

Le persone che effettivamente programmano il proprio algoritmo di ordinamento per qualche motivo tenderanno ad attenersi alla semplice variante a 2 vie perché il minor potenziale di errori supera il 20% di prestazioni migliori per la maggior parte del tempo. Ricorda: di gran lunga il miglioramento delle prestazioni più importante è quando il codice passa da "non funziona" a "funzionante".

In modo asintotico, non importa. Ad esempio, la ricerca binaria fa approssimativamente log ₂ n confronti, e la ricerca ternaria fa approssimativamente log ₃ n confronti. Se conosci i tuoi logaritmi, sai che il log _a x = log _b x / log _b a, quindi la ricerca binaria fa circa 1 / log ₃ 2 ≈ 1,5 volte tanti confronti rispetto alla ricerca ternaria. Questa è anche la ragione per cui nessuno specifica mai la base del logaritmo nella grande notazione Oh: è sempre un fattore costante lontano dal logaritmo in una data base, indipendentemente da quale sia la base effettiva. Quindi suddividere il problema in più sottoinsiemi non migliora la complessità del tempo e praticamente non è sufficiente per superare la logica più complessa. In effetti, questa complessità può influire negativamente sulle prestazioni pratiche, aumentando la pressione della cache o rendendo le micro-ottimizzazioni meno impraticabili.

D'altro canto, alcune strutture di dati tree-ish usano un fattore di ramificazione elevato (molto più grande di 3, spesso 32 o più), sebbene di solito per altri motivi. Migliora l'utilizzo della gerarchia della memoria: le strutture dati memorizzate nella RAM fanno un uso migliore della cache, le strutture dati memorizzate su disco richiedono meno letture HDD e gt; RAM.

Esistono algoritmi di ricerca / ordinamento che suddividono non per due, ma per N.

Un semplice esempio è la ricerca per codifica hash, che richiede tempo O (1).

Se la funzione di hash è di conservazione degli ordini, può essere usata per creare un algoritmo di ordinamento O (N). (Puoi pensare a qualsiasi algoritmo di ordinamento come solo fare N ricerche per dove dovrebbe andare un numero nel risultato.)

Il problema fondamentale è che, quando un programma esamina alcuni dati e poi inserisce alcuni stati seguenti, quanti stati seguenti sono presenti e quanto sono vicine le loro probabilità?

Quando un computer fa un confronto di due numeri, per esempio, e poi salta o meno, se entrambi i percorsi sono ugualmente probabili, il contatore del programma "conosce" un altro bit di informazione su ciascun percorso, quindi in media ha " imparato "un po '. Se un problema richiede che gli M bit vengano appresi, allora usando le decisioni binarie non è possibile ottenere la risposta in meno delle decisioni di M. Quindi, per esempio, cercare un numero in una tabella ordinata di 1024 non può essere fatto in meno di 10 decisioni binarie, se non altro perché un numero minore di risultati non sarebbe sufficiente, ma può certamente essere fatto in più.

Quando un computer prende un numero e lo trasforma in un indice in un array, "apprende" fino a registrare la base 2 del numero di elementi nell'array, e lo fa in tempo costante. Ad esempio, se c'è una tabella di salto di 1024 voci, tutte più o meno ugualmente probabili, quindi saltare attraverso quella tabella "impara" 10 bit. Questo è il trucco fondamentale dietro la codifica hash. Un esempio di classificazione di questo è come è possibile ordinare un mazzo di carte. Hai 52 bidoni, uno per ogni carta. Infila ogni carta nel suo contenitore, e poi raccogli tutte le carte. Nessuna suddivisione richiesta.

Poiché questa è una domanda sul divario e sulla conquista generali, non solo sull'ordinamento, sono sorpreso che nessuno abbia sollevato il Teorema Master

In breve, il tempo di esecuzione degli algoritmi divide e conquista è determinato da due forze di controrilancio: il beneficio derivante dal trasformare problemi più grandi in piccoli problemi e il prezzo da pagare nel dover risolvere più problemi. A seconda dei dettagli dell'algoritmo, può o non può pagare per dividere un problema in più di due pezzi. Se dividi lo stesso numero di sottoproblemi ad ogni passaggio e conosci la complessità temporale della combinazione dei risultati ad ogni passaggio, il Teorema principale ti dirà la complessità temporale dell'algoritmo complessivo.

L'algoritmo Karatsuba per la moltiplicazione utilizza una divisione e conquista a 3 vie per ottenere un tempo di esecuzione di O (3 n ^ log_2 3) che batte O (n ^ 2) per l'algoritmo di moltiplicazione ordinaria (n è il numero di cifre nei numeri).

A causa della sua natura binaria, un computer è molto efficiente nel dividere le cose in 2 e non tanto in 3. Ottieni una divisione in 3 dividendo prima in 2 e poi dividi nuovamente una delle parti in 2. Quindi se hai bisogno di dividere per 2 per ottenere la tua divisione 3, potresti anche dividere in 2.