radix-sort(a,d) // a[i] = c d...c 2 c 1 for j = 1 to d // a è ordinato rispetto alle cifre c...
TRANSCRIPT
Radix-Sort(A,d) // A[i] = cd...c2c1
for j = 1 to d // A è ordinato rispetto alle cifre cj-1...c1
“usa un algoritmo stabile per ordinare A rispetto alla j-esima cifra” // A è ordinato rispetto alle cifre cj...c1
// A è ordinato
Radix-Sort(A,d) // Complessità for j = 1 to d “usa Counting-Sort per ordinare A rispetto alla j-esima cifra”
))((),,( bndbdnT RS Complessità:
dove b è la base della numerazione e d è il numero di cifre dei numeri da ordinare.
Dovendo ordinare n numeri di m bit ciascuno possiamo scegliere r < m e suddividere i numeri in d=m/r “cifre” di r bit ciascunaIn questo caso la base della numerazione è b=2r e Radix-Sort richiede tempo ))2)(/(( rnrm
Quindi il valore ottimo di r dipende soltanto da n ed è approssimativamente log2 n.
La funzione ha un minimo per)2)(/()( rnrmrf r tale che nrr 22 log)12ln(log
Algoritmo Bucket-Sort
L’algoritmo Bucket-Sort assume che i valori da ordinare siano dei numeri reali in un intervallo semiaperto [a,b).
Per semplicità di esposizione assumiamo che l’intervallo sia [0,1).
1. Divide [0,1) in n parti uguali e inizializza un array B[0..n-1] di liste vuote (i bucket)
2. Mette in ciascuna lista B[k] gli elementi A[i] che cadono nella k-esima parte di [0,1)
3. Ordina ciascuna lista
4. Ricopia in A tutti gli elementi delle liste nell’ordine B[0],B[1],…,B[n-1]
Bucket-Sort per ordinare l’array A procede come segue:
A .781
.172
.393
.264
.725
.946
.217
.128
.239
.6810
B0 /
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
.78 /
.17 /
.39 /
.26 /
.72 /
.94 /
.21 /
.12 /
.23 /
.68 /
.12 / .17 /
.21 / .23 / .26 /
.72 / .78 /
.39 /
.68 /
.94 /
A .121
.172
.213
.234
.265
.396
.687
.728
.789
.9410
Bucket-Sort(A) n = A.length for i = 0 to n-1 “crea la lista vuota B[i]” for i = 1 to n “metti A[i] nella lista B[ nA[i] ]” // Gli elementi dell’array A sono stati tutti // inseriti nelle liste B[0],B[1],...,B[n-1] // Gli elementi di una lista B[i] sono minori degli // elementi della lista successiva B[i+1] for i = 0 to n-1 “ordina la lista B[i]” “copia in A le liste B[0],B[1],...,B[n-1]” // A è ordinato
Bucket-Sort(A) // Complessità
n = A.length //
for i = 0 to n-1
“crea la lista vuota B[i]” //
for i = 1 to n
“metti A[i] nella lista B[nA[i]]” //
for i = 0 to n-1
“ordina la lista B[i] con InsertSort” //
“copia in A le liste B[0],...,B[n-1]” //
)(n
)1(
)(n
1
0
2n
i inO
)(n
1
0
2)()(n
i iBS nOnnT
Nel caso peggiore in cui tutti gli elementi vanno a finire in un’unica lista abbiamo:
)()()()( 22max nOnOnnT BS
Nel caso migliore in cui gli elementi si distribuiscono uno per lista abbiamo:
)()()()(min nnOnnT BS Anche per il caso medio, se si assume che i valori in ingresso siano uniformemente distribuiti nell’intervallo [0,1), si dimostra che: )()(med nnT BS
Per dimostrarlo ci servono alcune semplici nozioni di calcolo delle probabilità.
Supponiamo di estrarre casualmente un valore x da un insieme X di possibili valori.
Non necessariamente tutti i valori x hanno la stessa probabilità di essere estratti.
Indichiamo con px la probabilità che venga estratto x
Xx
xxpX ]E[
Il valore medio che ci aspettiamo di ottenere si dice valore atteso di X ed è
1Xx
xpNaturalmente
Ad esempio se X è l’insieme delle possibili vincite alla roulette quando puntiamo 100 € su di un numero allora X contiene i due valori:
- 3600 € con probabilità 1/37 (si vince 36 volte la posta e i numeri della roulette sono 37 contando anche lo 0 dove vince sempre il banco) e
- 0 € con probabilità 36/37
Il valore atteso della vincita è allora
30.9737
360
37
13600]E[
XxxxpX
Dunque paghiamo 100 € per ricevere in media soltanto 97,30 € !!!!
Vediamo un altro esempio: X è l’insieme delle possibili vincite al Lotto quando puntiamo 100 € su di un terno.
X contiene i due valori: - 450000 € con probabilità 1/11748 (la vincita è 4500 volte
la posta e la probabilità che esca il terno è 1/11748) .- 0 € con probabilità 11747/11748.
Il valore atteso della vincita è allora
30.3811748
117470
11748
1450000]E[
XxxxpX
Dunque paghiamo 100 € per ricevere in media soltanto 38,30 €.Gli altri 61,70 € se li tiene lo stato come tassa sulla speranza
Il valore atteso gode delle seguenti proprietà:
]E[]E[]E[ YXYX qualunque siano le due variabili casuali X ed Y (anche se non sono tra loro indipendenti)Inoltre se le due variabili X ed Y sono indipendenti: ]E[]E[]E[ YXXY
Se c è una costante:
]E[]E[ YccY
Per ragioni di simmetria il valore atteso è lo stesso per tutte le liste.
Ci possiamo quindi limitare a calcolare il valore atteso relativo alla prima lista:
Tornando alla complessità media di Bucket-Sort e usando le proprietà del valore atteso:
)]E[()(
)]()(E[)(1
0
2
1
0
2med
n
i i
n
i iBS
nOn
nOnnT
]E[ 21n
Per calcolare definiamo le variabili casuali indicatrici
per cui
ni
iXn1
1
altrimenti0
[1] lista nella messo viene][ se1 BiAX i
Se A[i] è scelto casualmente, la variabile Xi ha valore 1 con probabilità 1/n e 0 con probabilità (n-1)/n.
Il valore atteso ènn
n
nX i
110
11]E[
ni
iXn1
1 1]E[]E[
]E[ 21n
Usando le variabili casuali indicatrici Xi possiamo calcolare:
][E]E[])E[(]E[
11
11
2
1
21
njni
ji
njni
jini
i XXXXXn
jinjni
jini
i XXX
111
2 ][E]E[]E[
nn
n
nX i
110
11]E[ 222
2
1]E[]E[
nXX ji
nnnn
nn
nnn
jinjnini
12
1)1(
111]E[
2
11
21
21
1
0
22 ]E[)()(
n
i iBS
med ncnnT
Quindi, assumendo che i valori siano dei reali uniformemente distribuiti in [0,1):
1
02 )1
2()(n
i ncn
)(2)( 22 ncncn
Algoritmi per statistiche d’ordine Problema della statistica d’ordine
Input: Un insieme A di n numeri ed un intero k compreso tra 1 ed n
Output: x A, k-esimo in ordine di grandezza
x A è il k-esimo in ordine di grandezza se gli altri n-1 elementi si possono ripartire in due gruppi: un gruppo di k-1 elementi tutti minori o uguali di x ed un gruppo di n-k elementi tutti maggiori o uguali di x.
Casi particolari:
k = 1 (minimo)
k = n (massimo)
k = (n+1)/2 (mediana inferiore o mediana)
k = (n+1)/2 (mediana superiore)
Minimo o massimo
Quanti confronti servono per trovare il minimo (o il massimo)?Minimo(A) // Massimo(A) è analogo min = A[1] for i = 2 to A.length
if min > A[i] min = A[i]
return min
n-1 confronti come limite superiore
Ma anche n-1 confronti come limite inferiore!
Possiamo escludere che un elemento sia il minimo soltanto dopo aver verificato che esso è maggiore di un altro!!
Dunque n-1 confronti è un limite stretto per calcolare il minimo e tale limite vale anche per il massimo.
Per escludere n-1 elementi servono quindi almeno n-1 confronti.
Min-Max(A) if A.length dispari max = min = A[1], i = 2 else if A[1] < A[2] min = A[1], max = A[2], i = 3 else min = A[2], max = A[1], i = 3
Minimo e massimo Quanti confronti servono per trovare assieme il minimo e il massimo?
while i ≤ A.length if A[i] < A[i+1]
if min > A[i] min = A[i]
if max < A[i+1] max = A[i+1] else
if min > A[i+1] min = A[i+1]
if max < A[i] max = A[i] i i+2 return min,max
se n dispari i confronti sono:
meno di 3 confronti ogni 2 elementi
nnn
2
3
2
3
2
3
2
13
se n pari i confronti sono:
nnn
2
32
2
3
2
231
Statistica d’ordine in tempo medio lineare
Il problema della statistica d’ordine:
Input: Un insieme A di n valori ed un intero k compreso tra 1 ed n
Output: x A, k-esimo in ordine di grandezza
Per semplicità supponiamo valori distinti
Si può risolvere in tempo medio lineare con un algoritmo Select ottenuto modificando Randomized-Quicksort
Complessità: minima O(n), massima O(n2)
Randomized-Select(A,p,r,k) // 1 ≤ k ≤ n if p == r return A[p] q = Randomized-Partition(A,p,r) // A[p..q-1] < A[q] < A[q+1..r] i = q - p+1 if k == i return A[q] elseif k < i return Randomized-Select(A,p,q-1,k) else return Randomized-Select(A,q+1,r,k-i)
r
pq
RSmed
RSmed qrpqT
nabnnT )),(max(
1)(
cT RSmed )1(
Limite superiore per la complessità media
1
0
))1,(max(1 n
i
RSmed iniT
nabn
spezzando la sommatoria in corrispondenza dell’elemento medio si ottiene
1
0
))1,(max(1
)(n
i
RSmed
RSmed iniT
nabnnT
1
2/)1(
2/)1(
0
)(1
)1(1 n
ni
RSmed
n
i
RSmed iT
ninT
nabn
dove il ≤ è dovuto al fatto che quando n è dispari il termine mediano viene sommato due volte.
1
2/)1(
2/)1(
0
)(1
)1(1 n
ni
RSmed
n
i
RSmed iT
ninT
nabn
1
2/)1(
)(2
)(n
ni
RSmed
RSmed iT
nabnnT
Con la sostituzione j = n - i - 1 nella prima sommatoria si ottiene
1
2/)1(
1
2/)1(
)(1
)(1 n
ni
RSmed
n
nj
RSmed iT
njT
nabn
Le due sommatorie sono uguali e quindi
Usiamo il metodo di sostituzione assumendo che la soluzione sia del tipo
21)( knknT RSmed
Se esistono due costanti k1 e k2 che soddisfano
per ogni n>1 abbiamo trovato la soluzione.
1
2/)1(
)(2
)(n
ni
RSmed
RSmed iT
nabnnT
cT RSmed )1(
Per n = 1 otteniamo k1 + k2 = cPer n > 1 dobbiamo dimostrare che
)()(
2 1
2/)1(
nTiTn
abn RSmed
n
ni
RSmed
Ossia sostituendo k1n + k2 da entrambe le parti
21
1
2
121 )(
2knkkik
nabn
n
ni
21
1
2
121 )(
2knkkik
nabn
n
ni
1
2
121
1
2
121 )
2
1(
2 )(
2 n
ni
n
ni
kn
kn
abnkikn
abn
2
1)
2
1(
2 21
nnk
nk
nabn
2)
22(
22
11 nk
kn
k
nabn
211
2)
2( k
kan
kb
è vera per ogni n se e
21211
2)
2( knkk
kan
kb
11
2k
kb 0
21
ka
La disequazione k1 + k2 = c per il caso base fornisce infine k2 = c - k1
ossia quando k1 ≤ 2b e k1 ≤ 2a
Dunque con k1 = min(2b,2a) e k2 = c - k1
21)( knknT RSmed
è una soluzione e quindi )()( nOnT RSmed