Analisi probabilistica di quicksort e quickselect

Quicksort e il suo parente quickselect sono gli esempi più puliti di analisi probabilistica: il caso pessimo è quadratico (Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →, Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →), ma scegliendo il pivot a caso il costo atteso è $\Theta(n\log n)$ per ogni input. Qui si calcola esattamente, con le variabili indicatrici di Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →.

Il modello

Chiavi tutte distinte (con ripetizioni basta una partizione a tre parti). Il costo è il numero di confronti tra chiavi: le altre operazioni (scambi, chiamate) sono proporzionali a questo.

import random

def quicksort(a, cnt):                 # cnt[0] conta i confronti
    if len(a) <= 1:
        return a
    p = random.choice(a)               # pivot uniforme tra gli elementi
    lo = [x for x in a if x < p]
    hi = [x for x in a if x > p]
    cnt[0] += len(a) - 1               # il pivot è confrontato con ogni altro elemento
    return quicksort(lo, cnt) + [p] + quicksort(hi, cnt)

Sia $C_n$ il numero di confronti su $n$ chiavi. Nei conti si indica con $z_1<z_2<\dots<z_n$ la sequenza ordinata delle chiavi: $z_i$ è l'elemento di rango $i$, qualunque sia la sua posizione iniziale.

Esempio (una esecuzione). $S=[5,2,9,1,6]$, quindi $z=(1,2,5,6,9)$. Pivot $6$: $4$ confronti, $lo=[5,2,1]$, $hi=[9]$. Su $[5,2,1]$ il pivot $2$: $2$ confronti, $lo=[1]$, $hi=[5]$. Totale $4+2=6$ confronti. Sono state confrontate le coppie $(6,5),(6,2),(6,1),(6,9)$ e $(2,1),(2,5)$; mai due volte la stessa coppia, perché dopo il confronto il pivot esce dal problema. Con altri pivot i confronti sarebbero stati tra $6$ (minimo per $n=5$) e $10=\binom52$ (caso pessimo).

Probabilità che due elementi vengano confrontati

Lemma. Per $i<j$, $z_i$ e $z_j$ sono confrontati (al più una volta) con probabilità $$P(z_i\text{ e }z_j\text{ confrontati})=\frac{2}{j-i+1}.$$

Dimostrazione. Sia $Z_{ij}=\{z_i,z_{i+1},\dots,z_j\}$, di $j-i+1$ elementi. Finché nessun elemento di $Z_{ij}$ è stato scelto come pivot, tutti restano nello stesso sottoproblema (un pivot esterno a $Z_{ij}$ è minore o maggiore di tutti, quindi li manda dalla stessa parte). Consideriamo il primo elemento di $Z_{ij}$ scelto come pivot: per simmetria è uniforme su $Z_{ij}$.

• Se è $z_i$ o $z_j$, viene confrontato con l'altro: confronto.
• Se è uno degli altri, $z_i$ e $z_j$ finiscono in parti diverse e non si incontreranno più: nessun confronto.

I casi favorevoli sono $2$ su $j-i+1$. $\square$

Esempio ($n=5$). Le coppie con $j-i=1$ (adiacenti) sono sempre confrontate: probabilità $\frac22=1$; con $j-i=2$: $\frac23$; con $j-i=3$: $\frac24=\frac12$; con $j-i=4$ ($z_1,z_5$): $\frac25$. Per $z_1,z_5$ vale $\frac25$: sono confrontati solo se il primo pivot dell'intero insieme è $z_1$ o $z_5$.

Numero atteso di confronti

Sia $X_{ij}=1$ se $z_i,z_j$ sono confrontati. Ogni coppia è confrontata al più una volta, quindi $C_n=\sum_{i<j}X_{ij}$ e per linearità $$E[C_n]=\sum_{1\le i<j\le n}\frac2{j-i+1}=\sum_{k=2}^{n}(n-k+1)\frac2k,$$ perché le coppie con $j-i+1=k$ sono $n-k+1$ (scelto $i$ da $1$ a $n-k+1$, $j=i+k-1$). Si separa $\frac{n-k+1}k=\frac{n+1}k-1$: $$E[C_n]=2(n+1)\sum_{k=2}^n\frac1k-2(n-1)=2(n+1)(H_n-1)-2(n-1)=2(n+1)H_n-4n.$$

Teorema. $E[C_n]=2(n+1)H_n-4n=2n\ln n-(4-2\gamma)\,n+2\ln n+O(1)$, con $4-2\gamma\approx2{,}846$. In particolare $E[C_n]\sim 2n\ln n\approx1{,}386\,n\log_2n$.

Esempi. $n=5$: la somma sulle coppie vale $4\cdot1+3\cdot\frac23+2\cdot\frac12+1\cdot\frac25=4+2+1+0{,}4=7{,}4$; la formula dà $2\cdot6\cdot\frac{137}{60}-20=27{,}4-20=7{,}4$. Altri valori: $E[C_2]=1$, $E[C_3]=\frac83$, $E[C_4]=\frac{29}6$, $E[C_6]=10{,}3$. Per $n=1000$: $E[C_n]\approx10\,986$, cioè $1{,}10\,n\log_2n$ (il coefficiente $1{,}386$ si raggiunge molto lentamente per il termine negativo $-2{,}846\,n$); contro $\binom{1000}2=499\,500$ del caso pessimo.

Ricorrenza alternativa

Dimostrazione senza coppie. Il pivot ha rango $k$ uniforme in $\{1..n\}$ (probabilità $\frac1n$ ciascuno); lascia sottoproblemi di taglia $k-1$ e $n-k$, ciascuno con la stessa distribuzione di partenza (su chiavi distinte). Condizionando sul rango (Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →, attesa condizionata): $$C_n=n-1+\frac1n\sum_{k=1}^n\big(C_{k-1}+C_{n-k}\big)=n-1+\frac2n\sum_{k=0}^{n-1}C_k,\qquad C_0=C_1=0$$ (qui $C_k$ indica l'attesa). Si moltiplica per $n$: $nC_n=n(n-1)+2\sum_{k<n}C_k$; scrivendo lo stesso per $n-1$ e sottraendo, la somma sparisce: $$nC_n-(n-1)C_{n-1}=2(n-1)+2C_{n-1}\;\Longrightarrow\;nC_n=(n+1)C_{n-1}+2(n-1).$$ Si divide per $n(n+1)$: $\frac{C_n}{n+1}=\frac{C_{n-1}}n+\frac{2(n-1)}{n(n+1)}$, e $\frac{2(n-1)}{n(n+1)}=\frac4{n+1}-\frac2n$ (denominatore comune: $\frac{4n-2(n+1)}{n(n+1)}$). Srotolando fino a $C_1=0$: $$\frac{C_n}{n+1}=\sum_{k=1}^n\Big(\frac4{k+1}-\frac2k\Big)=4(H_{n+1}-1)-2H_n=2H_n+\frac4{n+1}-4,$$ cioè $C_n=2(n+1)H_n-4n$, come sopra. Controllo: $\frac{C_2}3=\frac13$ e $\frac{C_1}2+\frac{2\cdot1}{2\cdot3}=\frac13$; $\frac{C_5}6=\frac{37}{30}$.

Pivot casuale o input casuale

Due modelli diversi danno la stessa media:

1. Algoritmo randomizzato: pivot uniforme, input qualunque (anche il peggiore). La media è su scelte dell'algoritmo, sempre $2(n+1)H_n-4n$.
2. Analisi del caso medio: pivot fisso (per esempio l'ultimo), input permutazione uniforme. Il pivot ha rango uniforme e, dato il rango, le due parti sono ancora permutazioni uniformi dei loro elementi: la ricorrenza è la stessa. Con $n=5$ la media sulle $120$ permutazioni è $\frac{37}5=7{,}4$.

La differenza è che nel secondo caso un input ordinato dà sempre $\binom n2$ confronti (per $n=6$: $15$), mentre nel primo nessun input è peggiore degli altri: la probabilità di toccare il caso pessimo è piccola.

Proprietà. Il caso pessimo $\binom n2$ è raggiunto solo se ogni pivot è il minimo o il massimo del suo sottoproblema. Un sottoproblema di taglia $m\ge2$ lo permette con probabilità $\frac2m$, quindi $P(C_n=\binom n2)=\prod_{m=2}^n\frac2m=\frac{2^{n-1}}{n!}$.

Esempio. $n=6$: $\frac{2^5}{720}=\frac2{45}\approx0{,}044$; $n=10$: $\frac{512}{3\,628\,800}\approx1{,}4\cdot10^{-4}$. Per $n=4$ la distribuzione esatta è $C_4=4$ con probabilità $\frac12$, $5$ con $\frac16$, $6$ con $\frac13$, media $2+\frac56+2=\frac{29}6$.

Las Vegas. Quicksort randomizzato è sempre corretto e ha tempo aleatorio. Per Markov (Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →) $P(C_n\ge c\,E[C_n])\le\frac1c$: la probabilità di costare più di $4$ volte la media è al più $\frac14$. È una stima debole (la vera probabilità di superare di un fattore costante la media è molto più piccola, come si dimostra con i metodi di Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata → e Limiti di Chernoff e di HoeffdingMarkov applicato a e^(tX) dà code esponenziali. Per somme di Bernoulli indipendenti con media μ: P(X ≥ (1+δ)μ) ≤ [e^δ/(1+δ)^(1+δ)]^μ ≤ e^(-δ²μ/3) per 0<δ≤1, P(X ≤ (1-δ)μ) ≤ e^(-δ²μ/2), P(X ≥ R) ≤ 2^(-R) se R ≥ 6μ. Hoeffding per X_i in [a_i,b_i]: P(|S-E[S]| ≥ t) ≤ 2exp(-2t²/Σ(b_i-a_i)²). Applicazioni: n ≥ ln(2/δ)/(2ε²) campioni per stimare una probabilità, amplificazione BPP con k = O(log 1/ε) ripetizioni, bilanciamento di insiemi con scarto √(4m ln n).Limiti di Chernoff e di Hoeffding →).

Quickselect

Problema: dato un insieme di $n$ chiavi distinte, trovare l'elemento di rango $k$ (la selezione; $k=\lceil n/2\rceil$ è la mediana) senza ordinare tutto.

def quickselect(a, k, cnt):            # k-esimo più piccolo, k da 1
    while True:
        p = random.choice(a)
        lo = [x for x in a if x < p]
        hi = [x for x in a if x > p]
        cnt[0] += len(a) - 1
        if k <= len(lo):
            a = lo
        elif k == len(lo) + 1:
            return p
        else:
            k -= len(lo) + 1
            a = hi

Dopo il pivot si scende in una sola parte (quella che contiene il rango cercato). Esempio: $S=[7,3,9,1,5,8]$, $k=3$ (la risposta è $5$). Pivot $8$: $5$ confronti, $lo=[7,3,1,5]$ (4 elementi, $k=3\le4$). Pivot $3$: $3$ confronti, $lo=[1]$, $k=3>1+1$, quindi $k=3-2=1$ e $a=hi=[7,5]$. Pivot $7$: $1$ confronto, $lo=[5]$, $k=1\le1$; poi pivot $5$ di un elemento e $k=1=0+1$: ritorna $5$. Totale $5+3+1=9$ confronti.

Teorema. Il numero atteso di confronti di quickselect su $n$ elementi è al più $4n$, per ogni $k$.

Dimostrazione (induzione). Sia $T(n)$ il massimo su $k$ dell'attesa. Il pivot ha rango $r$ uniforme; costa $n-1$ confronti e si prosegue in un sottoproblema di taglia al più $m_r=\max(r-1,n-r)$. Quindi $T(n)\le n-1+\frac1n\sum_{r=1}^nT(m_r)$. I valori $m_r$ vanno da $\lfloor n/2\rfloor$ a $n-1$, ciascuno al più due volte. Per ipotesi induttiva $T(m)\le4m$ e $$T(n)\le n-1+\frac4n\cdot2\!\!\sum_{m=\lfloor n/2\rfloor}^{n-1}\!\!m\le n-1+\frac8n\cdot\frac{3n^2}8=n-1+3n\le4n,$$ dove $\sum_{m=\lfloor n/2\rfloor}^{n-1}m\le\frac{3n^2}8$ (per $n$ pari vale $\frac{n(3n-2)}8$; per $n$ dispari $\frac{3(n^2-1)}8$). $\square$

Il motivo: con probabilità $\frac12$ il pivot è nella metà centrale e l'insieme cala almeno di un quarto; le taglie decrescono in modo geometrico e la somma $n+\frac34n+(\frac34)^2n+\dots=4n$.

Valore esatto. Con la stessa tecnica della ricorrenza si ottiene $$E[C_{n,k}]=2\Big(n+3+(n+1)H_n-(k+2)H_k-(n+3-k)H_{n+1-k}\Big).$$ Per $k=1$ (il minimo) diventa $2(n-H_n)$: per $n=10$ è $14{,}14$. Per la mediana $E[C_{n,\lceil n/2\rceil}]\approx2(1+\ln2)\,n\approx3{,}39\,n$ ($n=1001$: $3340\approx3{,}34\,n$). Cercare il minimo con quickselect costa quindi circa $2n$: il doppio dei $n-1$ confronti della scansione lineare, ma l'algoritmo vale per ogni $k$. Nel caso pessimo il costo di quickselect è $\binom n2$, ma con probabilità trascurabile; esiste anche un algoritmo deterministico lineare nel caso pessimo, molto più complicato.

Domande d'esame

1. Dimostra che $z_i,z_j$ sono confrontati con probabilità $\frac2{j-i+1}$. Si considera il primo pivot scelto in $Z_{ij}=\{z_i..z_j\}$: uniforme su $j-i+1$ elementi, e si confronta solo se è $z_i$ o $z_j$.
2. Calcola $E[C_5]$. $\sum_{i<j}\frac2{j-i+1}=4+2+1+\frac25=7{,}4=2\cdot6\cdot H_5-20$.
3. Probabilità che quicksort randomizzato su $6$ elementi faccia il numero massimo di confronti. $\frac{2^5}{6!}=\frac2{45}$, perché ogni pivot deve essere un estremo.
4. Perché quickselect è lineare mentre quicksort no? Si scende in una sola parte e il costo $n-1$ per livello decresce in modo geometrico: $E[T(n)]\le n-1+\frac1n\sum T(m_r)$ con soluzione $4n$.