Salta al contenuto
Note per Studenti Esercizio - ricorrenza di quicksort, forma chiusa e confronto con n log n

Esercizio - ricorrenza di quicksort, forma chiusa e confronto con n log n

Teoria: Analisi probabilistica di quicksort e quickselectCon pivot casuale due elementi di rango $i<j$ vengono confrontati con probabilità $2/(j-i+1)$; sommando sulle coppie il numero atteso di confronti di quicksort è esattamente $2(n+1)H_n-4n\approx2n\ln n-2{,}85,n$ (stessa formula dalla ricorrenza $C_n=n-1+\frac2n\sum_{k<n}C_k$). Quickselect trova il $k$-esimo elemento con attesa lineare, al più $4n$ confronti (mediana $\approx3{,}39,n$). Pivot fisso su input casuale equivale a pivot casuale su input qualunque.Analisi probabilistica di quicksort e quickselect → (ricorrenza alternativa), Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →.

Testo. Sia CnC_n il numero atteso di confronti di quicksort con pivot casuale su nn chiavi distinte.

  1. Scrivere la ricorrenza Cn=n−1+2n∑k=0n−1CkC_n=n-1+\frac2n\sum_{k=0}^{n-1}C_k (con C0=C1=0C_0=C_1=0) e spiegarla.
  2. Trasformarla nella ricorrenza a un solo termine nCn=(n+1)Cn−1+2(n−1)nC_n=(n+1)C_{n-1}+2(n-1) e risolverla.
  3. Calcolare C1,…,C8C_1,\dots,C_8.
  4. Per n=1000n=1000 e n=106n=10^6 calcolare CnC_n e confrontarlo con nlog⁡2nn\log_2n e con (n2)\binom n2.

Soluzione

1. Ricorrenza. Il pivot ha rango k∈{1..n}k\in\{1..n\} con probabilità 1n\frac1n ciascuno; la partizione costa n−1n-1 confronti e lascia due sottoproblemi di taglie k−1k-1 e n−kn-k, ancora su chiavi distinte e in ordine "casuale" per le scelte del pivot. Per probabilità totale sul rango (attesa condizionata: 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 →) Cn=n−1+1n∑k=1n(Ck−1+Cn−k)=n−1+2n∑k=0n−1Ck,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, perché le due somme ∑kCk−1\sum_kC_{k-1} e ∑kCn−k\sum_kC_{n-k} contengono gli stessi addendi C0..Cn−1C_0..C_{n-1}.

2. Un solo termine. Si moltiplica per nn: nCn=n(n−1)+2∑k<nCknC_n=n(n-1)+2\sum_{k<n}C_k. La stessa uguaglianza per n−1n-1 è (n−1)Cn−1=(n−1)(n−2)+2∑k<n−1Ck(n-1)C_{n-1}=(n-1)(n-2)+2\sum_{k<n-1}C_k. Sottraendo, la somma si riduce al solo termine Cn−1C_{n-1}: nCn−(n−1)Cn−1=n(n−1)−(n−1)(n−2)+2Cn−1=2(n−1)+2Cn−1  ⟹  nCn=(n+1)Cn−1+2(n−1).nC_n-(n-1)C_{n-1}=n(n-1)-(n-1)(n-2)+2C_{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)n(n+1) per ottenere un telescopio: Cnn+1=Cn−1n+2(n−1)n(n+1)\frac{C_n}{n+1}=\frac{C_{n-1}}n+\frac{2(n-1)}{n(n+1)} e 2(n−1)n(n+1)=4n+1−2n\frac{2(n-1)}{n(n+1)}=\frac4{n+1}-\frac2n (denominatore comune: 4n−2n−2n(n+1)\frac{4n-2n-2}{n(n+1)}). Srotolando fino a C12=0\frac{C_1}2=0: Cnn+1=∑k=2n(4k+1−2k)=4(Hn+1−32)−2(Hn−1)=2Hn+4n+1−4,\frac{C_n}{n+1}=\sum_{k=2}^n\Big(\frac4{k+1}-\frac2k\Big)=4\big(H_{n+1}-\tfrac32\big)-2\big(H_n-1\big)=2H_n+\frac4{n+1}-4, dove ∑k=2n4k+1=4(Hn+1−1−12)\sum_{k=2}^n\frac4{k+1}=4(H_{n+1}-1-\frac12). Quindi Cn=2(n+1)Hn+4−4(n+1)=2(n+1)Hn−4nC_n=2(n+1)H_n+4-4(n+1)=2(n+1)H_n-4n.

3. Valori. Dalla ricorrenza a un termine: C2=3C1+22=1C_2=\frac{3C_1+2}{2}=1; C3=4C2+43=83C_3=\frac{4C_2+4}3=\frac83; C4=5C3+64=40/3+64=296C_4=\frac{5C_3+6}4=\frac{40/3+6}4=\frac{29}6; C5=6C4+85=29+85=375C_5=\frac{6C_4+8}5=\frac{29+8}5=\frac{37}5; C6=7C5+106=51,8+106=10310C_6=\frac{7C_5+10}6=\frac{51{,}8+10}6=\frac{103}{10}; C7=8C6+127=82,4+127=47235≈13,486C_7=\frac{8C_6+12}7=\frac{82{,}4+12}7=\frac{472}{35}\approx13{,}486; C8=9C7+148=121,37+148=2369140≈16,921C_8=\frac{9C_7+14}8=\frac{121{,}37+14}{8}=\frac{2369}{140}\approx16{,}921. La formula dà gli stessi valori (per esempio C6=2⋅7⋅4920−24=34,3−24=10,3C_6=2\cdot7\cdot\frac{49}{20}-24=34{,}3-24=10{,}3).

4. Taglie grandi. Con Hn=ln⁡n+γ+12nH_n=\ln n+\gamma+\frac1{2n}:

  • n=1000n=1000: Cn=2⋅1001⋅7,48547−4000=10 986C_n=2\cdot1001\cdot7{,}48547-4000=10\,986; nlog⁡2n=9966n\log_2n=9966 (rapporto 1,101{,}10); (n2)=499 500\binom n2=499\,500.
  • n=106n=10^6: Cn≈2,4785⋅107C_n\approx2{,}4785\cdot10^7; nlog⁡2n=1,993⋅107n\log_2n=1{,}993\cdot10^7 (rapporto 1,241{,}24, che tende a 2ln⁡2=1,3862\ln2=1{,}386); (n2)=5⋅1011\binom n2=5\cdot10^{11}: il caso pessimo è 20 00020\,000 volte più grande della media.

Risultato. Cn=2(n+1)Hn−4nC_n=2(n+1)H_n-4n; C1..C8=0, 1, 83, 296, 375, 10310, 47235, 2369140C_1..C_8=0,\,1,\,\frac83,\,\frac{29}6,\,\frac{37}5,\,\frac{103}{10},\,\frac{472}{35},\,\frac{2369}{140}; C1000≈10 986C_{1000}\approx10\,986, C106≈2,48⋅107C_{10^6}\approx2{,}48\cdot10^7.

Verifica Python: ricorrenza risolta con Fraction e confronto con la formula chiusa per n≤8n\le8 (uguaglianza esatta); simulazione di 300300 ordinamenti con n=1000n=1000: media 11 01411\,014 (scarto dalla media esatta 2828, compatibile con l'errore statistico).

Versione ripasso

Teoria collegata