Cercando di capire il 2N lNN confronta per quicksort

La funzione di costo C per quicksort consiste di due parti. La prima parte è il costo del partizionamento dell'array in due "metà" (le metà non devono essere di dimensioni uguali, quindi le virgolette). La seconda parte è il costo dell'ordinamento di queste due metà.

1. Il termine (N + 1) è in realtà un termine condensato e deriva dai termini

   (N - 1) + 2
   

   Questo è il costo del partizionamento in quicksort: N-1 confronta con il valore pivot e 2 ulteriori confronti dovuti ad alcune condizioni al contorno nel partizionamento.

2. La seconda parte dell'equazione è costituita dai costi per l'ordinamento delle due "metà" su entrambi i lati del valore pivot k .

   Dopo aver scelto un valore pivot, ti rimangono due "metà" non ordinate. Il costo dell'ordinamento di queste "metà" dipende dalla loro dimensione ed è più semplice descritto come un'applicazione ricorsiva della funzione di costo C . Se il pivot è il più piccolo dei valori di N , i costi per l'ordinamento di ciascuna delle due "metà" sono rispettivamente C(0) e C(N-1) (il costo per l'ordinamento di un array con 0 elementi e il costo per l'ordinamento con N-1 elementi). Se il pivot è il quinto più piccolo, il costo per l'ordinamento di ciascuna delle due "metà" è rispettivamente C(5) e C(N-6) (il costo per l'ordinamento di un array con 5 elementi e il costo per l'ordinamento di uno con N-6 elementi). E allo stesso modo per tutti gli altri valori pivot.

   Ma quanto costa ordinare quei due "mezzi" se non si conosce il valore del pivot? Questo viene fatto prendendo il costo per ogni possibile valore del pivot e moltiplicandolo per la possibilità che quel particolare valore si presenti.

   Poiché ogni valore pivot è ugualmente probabile, la possibilità di scegliere un particolare valore pivot è 1/N se hai N elementi. Per capire questo, pensa a tirare un dado. Con un dado appropriato, la possibilità per ciascun lato di essere rivolto verso l'alto è uguale, quindi la possibilità di tirare un 1 è 1/6.

   Combinato, questo fornisce il termine di sommatoria in cui, per ogni possibile valore k del pivot, il costo ( C(k-1) + C(N-k) ) viene moltiplicato per il caso ( 1/N )

3. L'ulteriore derivazione del formule di sommatoria nella domanda per 2N lnN nel titolo richiede troppa matematica per spiegare nel dettaglio, ma è basata sulla comprensione del costo per l'ordinamento di una matrice di% co_de Gli elementi% ( N ) possono essere espressi in termini di ordinamento di una matrice di C(N) elementi ( N-1 ) e un fattore direttamente proporzionale a C(N-1) .

1. Sembra che N + 1 come numero di confronti per il passo della partizione sia un errore nel libro. È necessario scoprire per ciascuno degli elementi N-1 non pivot se è minore o maggiore del pivot, che richiede un confronto; quindi confronti N-1 in totale, non N + 1. (Si consideri il caso più semplice, N = 2, cioè un pivot e un altro elemento: non c'è assolutamente spazio per fare tre confronti tra due elementi.)

2. Considera il caso in cui il perno scelto risulta essere l'elemento più piccolo (k = 1). Ciò significa che l'array è diviso in una parte vuota a sinistra (non ci sono elementi che sono meno del pivot) e una parte a destra che contiene tutti gli elementi ad eccezione del pivot (tutti gli altri elementi sono maggiori del pivot ). Ciò significa che i sotto-problemi che ora si vogliono risolvere ricorsivamente hanno dimensioni 0 e N-1 (k-1 e N-k), rispettivamente, e richiedono confronti C (0) e C (N-1); quindi, C (0) + C (N-1) in totale.

   Se il pivot risulta essere il secondo elemento più piccolo (k = 2), le dimensioni dei problemi secondari sono 1 e N-2 (k-1 e N-k; un elemento a sinistra, perché è l'unico uno più piccolo del perno). Pertanto, la risoluzione ricorsiva di questi sotto-problemi richiede confronti C (1) + C (N-2). E così via se il pivot è il terzo elemento più piccolo, il quarto, ecc. Queste sono le espressioni nei numeratori.

   Poiché il pivot viene scelto casualmente tra gli elementi N, ogni caso (pivot è il più piccolo, pivot è il secondo più piccolo, ecc.) si verifica con uguale probabilità 1 / N. Ecco da dove viene la N dei denominatori.