quicksort randomizzato: probabilità del confronto di due elementi?

Question

Sto leggendo "Probability and Computing" di M.Mitzenmacher e E.Upfal. Sto avendo problemi a capire come viene calcolata la probabilità di confronto tra due elementi.

Ingresso: elenco ordinato (y1, y2, ..., yN) di numeri. Stiamo cercando un elemento pivot (a caso). Domanda: qual è la probabilità che due elementi yi e yj (j> i) saranno confrontati?

Risposta (dal libro): yi e yj sarà confrontata se uno yi yj saranno selezionati come pivot in prima estrazione dalla sequenza (yi, yi + 1, ..., yj-1, yj) . Quindi la probabilità è: 2/(j-i + 1).

Il problema per me è la rivendicazione iniziale: ad esempio, raccogliere yi nella prima estrazione dall'elenco completo causerà il confronto con yj (e viceversa) e la probabilità è 2/n.

Quindi, l'affermazione "inversa" è vera: nessuno degli elementi (yi + 1, ..., yj-1) può essere selezionato prima di yi o yj, ma la dimensione "pool" non è fissa (nel primo pareggio è sicuramente N, ma nel secondo è più piccolo).

Qualcuno potrebbe spiegare come gli autori hanno trovato una conclusione così semplificata?

Edit1: un po 'di buona anima ha lucidato il mio post, grazie :-).

Edit2: l'elenco è ordinato inizialmente.

Answer 1

La risposta fornita dagli autori è corretta, anche se non vedo ancora come siano arrivati ​​alla conclusione che sia facile e veloce.

Indichiamo con L = j-i + 1. I valori effettivi di je non contano qui, ciò che conta è L. Denotiamo anche con P (N, L) la probabilità di confrontare l'elemento yi yj dalla sequenza ordinata di numeri di dimensione N.

Fatti:

• P (N, 2) = 1
• P (N, L) = 2/N + 1/N * (P (N-1, L) + P (N-2, L) + P (N-3, L) + ... + P (L, L))

Questa somma sembra brutta, ma dopo due test è risultato che P (N, L) è probabilmente uguale a 2/L. Controlliamo fuori:

• P (N, L = 2) = 1 = 2/2 = 2/L
• supponiamo P (N, L) = 2/L
• P (N + 1, L) = 2/(N + 1) + 1/(N + 1) * (P (N, L) + ... P (L, L)) = 2/(N + 1) + (N-L + 1) * 1/(N + 1) * 2/L = 2/L

E poiché L = j-i + 1, otteniamo 2/(j-i + 1).

Answer 2

Quicksort funziona confrontando ciascun elemento con il pivot: quelli più grandi del pivot sono posizionati a destra del pivot e quelli non più grandi a sinistra (o viceversa se si desidera un ordinamento decrescente, non lo fa non importa).

Ad ogni passaggio, il perno viene scelto da una sequenza (yi, yi+1, ..., yj). Quanti elementi in questa sequenza? j - i + 1 (Penso che tu abbia avuto un errore di battitura, non può essere y - i + 1).

Quindi la probabilità di selezionare uno dei due elementi specifici da questo elenco è ovviamente 2/(j - i + 1).

Il problema per me è la rivendicazione iniziale: ad esempio, raccogliere yi nella prima estrazione dall'elenco completo causerà il confronto con yj (e viceversa) e la probabilità è 2/n.

Sollevare yi farà sì che essere confrontato con gli altri j - i unici elementi. Da dove hai preso n? Ricorda che la tua lista va solo da yi a yj!

Edit:

Lettura di nuovo la domanda, io lo trovo un po 'ambiguo. La probabilità di confrontare due elementi al primo passaggio della ricorsione è effettivamente 2/n come dici tu, perché lo i e lo j sono 1 e n. La probabilità di confrontare due elementi in un passo ricorsivo sconosciuto è ciò che ho spiegato sopra.