Selezione mediana ottimale della mediana - 3 blocchi di elementi contro 5 blocchi di elementi?

Question

Sto lavorando a un'implementazione variante Quicksort basata su the Select algorithm per la scelta di un elemento di pivot buona. La saggezza convenzionale sembra essere quella di dividere l'array in blocchi di 5 elementi, prendere la mediana di ciascuno, e quindi applicare ricorsivamente lo stesso approccio di blocco alle mediane risultanti per ottenere una "mediana delle mediane".

Ciò che mi confonde è la scelta di blocchi a 5 elementi anziché di blocchi a 3 elementi. Con blocchi a 5 elementi, mi sembra che tu esegua le operazioni di mediana-of-5 n/4 = n/5 + n/25 + n/125 + n/625 + ..., mentre con i blocchi a 3 elementi, esegui le operazioni di mediana-3 di n/2 = n/3 + n/9 + n/27 + n/81 + .... Essendo che ogni mediana-di-5 è di 6 confronti, e ogni mediana-di-3 è 2 confronti, che si traduce in confronti 3*n/2 utilizzando i confronti di mediana di 5 e n utilizzando la mediana di 3.

Qualcuno può spiegare questa discrepanza e quale potrebbe essere la motivazione per l'utilizzo di blocchi a 5 elementi? Non ho familiarità con le consuete pratiche per l'applicazione di questi algoritmi, quindi forse c'è un modo per tagliare alcuni passaggi e ottenere ancora "abbastanza vicino" alla mediana per garantire un buon pivot, e tale approccio funziona meglio con i blocchi a 5 elementi ?

Answer 1

Il motivo è che scegliendo blocchi di 3, potremmo perdere la garanzia di avere un algoritmo di tempo O (n).

per blocchi di 5, la complessità temporale è

T (n) = T (n/5) + T (7n/10) + O (n)

Per blocchi 3, essa risulta essere

T (n) = T (n/3) + T (2n/3) + O (n)

check this out: http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

Answer 2

credo che abbia a che fare con l'assicurazione di una "buona" divisione. La divisione in blocchi a 5 elementi assicura una suddivisione del caso peggiore di 70-30. L'argomento standard è simile al seguente: dei blocchi n/5, almeno la metà delle mediane è> = la mediana-dei-mediani, quindi almeno la metà dei blocchi n/5 ha almeno 3 elementi (1/2 di 5)> = mediana-di-mediana, e questo dà una divisione 3n/10, il che significa che l'altra partizione è 7n/10 nel peggiore dei casi.

Che dà T(n) = T(n/5) + T(7n/10) + O(n).

Dal n/5 + 7n/10 < 1, il caso peggiore tempo di esecuzione è O (n).

scelta blocchi di 3 elementi rende così: almeno la metà dei n/3 blocchi hanno almeno 2 elementi> = mediana-di-mediane, quindi questo dà una scissione n/3 o 2n/3 nel caso peggiore.

Che dà T(n) = T(n/3) + T(2n/3) + O(n).

In questo caso, n/3 + 2n/3 = 1, quindi si riduce a O (n log n) nel peggiore dei casi.

Answer 3

È possibile utilizzare blocchi di dimensione 3! Sì, sono sorpreso quanto te. Nel 2014 (hai chiesto nel 2010) è arrivato un documento che mostra come farlo.

L'idea è la seguente: invece di fare median3, partition, median3, partition, ..., fate median3, median3, partition, median3, median3, partition, .... Nella carta questo è chiamato "L'algoritmo del passo ripetuto".

Così, invece di:

T(n) <= T(n/3) + T(2n/3) + O(n) 
T(n) = O(nlogn) 

si ottiene:

T(n) <= T(n/9) + T(7n/9) + O(n) 
T(n) = Theta(n) 

Il suddetto articolo è Select with Groups of 3 or 4 Takes Linear Time da K. Chen e A. Dumitrescu (2014, arXiv), o Select with groups of 3 or 4 (2015, autore di homepage).

PS: Il Fast Deterministic Selection di A. Alexandrescu (of fame Lingua D!), Che mostra come implementare quanto sopra ancora più efficiente.