Probabilità che due elementi siano confrontati in rapido randomizzato

Question

Sto avendo un problema in una parte specifica dell'analisi rapida randomizzata.

Secondo l'algoritmo rapido randomizzato il pivot viene scelto dal sottoinsieme dato su cui è chiamato da un indice casuale, invece di scegliere semplicemente un indice specifico ogni volta.

Ora supponiamo di dare una serie di dimensioni di dimensioni $ N $ al nostro algoritmo randomizzato Quicksort.

Ora chiedo di dare un'occhiata alla prova di Lemma-7.1 nel testo fornito di seguito. Ora abbiamo dato un array al nostro algoritmo che può essere di qualsiasi permutazione degli elementi, ma nel paragrafo subito dopo la prova di $ Lemma-7.1 $ .

Perché l'autore considera un'istanza ordinata del nostro array di ingresso mentre si esegue l'analisi?

Inoltre se guarda il testo dopo l'equazione $ (7.2) $ dove c'è giustificato la loro logica di trovare la probabilità che $ z_i $ deve essere confrontato con $ z_j $ nel nostro algoritmo. Ora, stanno considerando il sottoinsieme { $ z_i $ , ..., $ z_j $ }. Non è questo caso di confronto di $ z_i $ , $ z_j $ diventando troppo specifico se consideriamo questo Sottosieme specifico solo? Intendo dire che stiamo usando approccio randomizzato e la probabilità di confronto potrebbe essere derivata utilizzando un aspetto più ampio, come una permutazione di tutti i casi possibili o giù di lì.

Che stiamo usando un sottoinsieme specifico e troppo ordinato non è convincente su come stiamo ottenendo la probabilità corretta per il nostro algoritmo ...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

.

E la probabilità di $ 1 / (J-I + 1) $ -> Totale no. di elementi nel sottoinsieme è anche fissato per specifico $ i $ e $ j $

Nel considerare la probabilità di confronto di $ z_i $ , $ z_j $ , il sottoinsieme in cui I due elementi sono lì e che devono essere partizionati può essere qualsiasi cosa (cioè composto da qualsiasi elemento possibile) e di qualsiasi dimensione (non solo $ j-i + 1 $ ) ...

potrebbe essere la condizione della randomizzazione in realtà prendendo tutto in account ma non lo sto ottenendo. Per favore, puoi spiegarmi la logica che stanno usando per trovare la suddetta probabilità e ti preghiamo di convincermi che stiamo correttamente troviamo la probabilità di confronto.

per riferimento Sto collegando le pagine corrispondenti di Introduzione agli algoritmi 3RD ED-- CLRS

Answer 1

Una prova molto semplice: rivendico che se ci sono intergi D con valori tra X e Y, e ci sono n ≥ 2 elementi nell'array, quindi la probabilità che X e Y siano confrontati sia 2 / (D + 2 ), indipendente da n.

Proof per induzione: se n= 2 poi chiaramente d= 0, quindi il reclamo è che x e y viene confrontato con probabilità 2 / (0 + 2)= 1. Questo è anche chiaramente corretto, dal momento che X e Y essere confrontato.

Ora lascia che n ≥ 3. Per il primo partizionamento, scegliamo un pivot a caso. Ogni elemento di array viene confrontato contro il perno, e non vengono fatti altri confronti. Quindi, se per coincidenza scegliamo x o y come il perno, x e y sarà confrontato. La probabilità per questo è 2 / n. Se per coincidenza scegliamo uno degli elementi D con valori tra X e Y, quindi il partizionamento si muoverà x a una partizione e Y all'altro, quindi non vengono mai confrontati. Se scegliamo uno degli altri elementi N - D - 2, quindi X e Y finiscono nella stessa partizione, e per induzione saranno confrontati con probabilità 2 / (D + 2).

Quindi la probabilità che x e y siano confrontati sia

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

.

è ovviamente lo stesso risultato di Yuval's, da | J - I |= D + 1. Il randomisting rende l'analisi abbastanza facile - se abbiamo detto ad esempio "Se N> 5 poi prendiamo 5 elementi a caso e scegli la mediana di quei 5 come pivot", l'analisi sarebbe molto più complessa.

PS. La prova nella carta è molto più semplice: mentre si separa l'array, $ x_i $ e $ x_j $ rimanere nella stessa sotto-partizione fino a quando un pivot con I <= pivot <= j viene utilizzato. Se quel pivot è io o j allora $ x_i $ e $ x_j $ sono confrontati, altrimenti non lo sono rispetto. Quindi la possibilità è 2 / (ABS (ABS (J-I) + 1).

Answer 2

L'idea della prova è quella di calcolare, per due elementi $ x, y $ nell'array, la probabilità che siano confrontati nell'algoritmo. Questa probabilità potrebbe potenzialmente dipendere dall'intero array. Tuttavia, si scopre che è possibile calcolarlo solo data le statistiche dell'ordine di $ x, y $ , cioè il loro ordine relativo nell'array ordinata. Se lo sai che $ x $ è la $ i $ l'elemento più piccolo nell'array e quella $ y $ è la $ j $ L'elemento più piccolo nell'array, quindi la probabilità che $ x, y $ sono confrontati è $ \ frac {2} {| ji | +1} $ .

Questo non è un caso speciale - ogni elemento $ x $ nell'array è la $ I $ L'elemento più piccolo, per un certo valore di $ i $ . Questa è solo le informazioni pertinenti che ci consentono di calcolare la probabilità che $ x $ e $ y $ sono rispetto.