Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Strategie per la progettazione di algoritmi:
divide & conquer
• problema del min-max
• quicksort
Copyright © 2007-2008 by Claudio Salati.
Lez. 10a
1
DIVIDE-&-CONQUER
•
Nella progettazione di un algoritmo la strategia e' quasi sempre
quella di suddividere il problema in sottoproblemi piu' semplici.
•
Dato un problema P su un insieme di dati di dimensione n una
maniera di suddividerlo in problemi piu' semplici e' quella di
considerare problemi analoghi a P ma su insiemi di dati di
dimensione minore
(cioe' problemi piu' piccoli: piccolo e' facile)
•
SI RICONDUCE LA SOLUZIONE DI P, dove #P = n, ALLA
SOLUZIONE DI m PROBLEMI P1, P2, …, Pm,
dove  i | 1i m : # Pi = n/k
•
OVVIAMENTE BISOGNA CHE SIA FACILE:
•
OPERARE LA SCOMPOSIZIONE
•
RICOMPORRE LE m SOLUZIONI PARZIALI NELLA
SOLUZIONE COMPLESSIVA
2
DIVIDE-&-CONQUER
•
PERCHE' CONSIDERARE LO STESSO PROBLEMA SOLO
PER DIMENSIONI PIU' PICCOLE DOVREBBE ESSERE
CONVENIENTE?
•
PERCHE' SE IL PROBLEMA E' DI COMPLESSITA' n2
DIVIDERLO PER 2 SIGNIFICA OTTENERE UN PROBLEMA 4
VOLTE PIU' FACILE!
•
Non solo, OPERANDO RICORSIVAMENTE SI ARRIVA AD
OTTENERE PROBLEMI ELEMENTARI:
 e.g., ORDINARE UN VETTORE DI LUNGHEZZA 1 E'
MOLTO FACILE, E' GIA' DI PER SE STESSO
ORDINATO
3
DIVIDE-&-CONQUER
void divideAndConquer(items data [],
int fromItem, int toItem) {
// risolve il problema per il sottovettore
// data[fromItem..toItem];
// la risoluzione si suppone sul posto
if (smallEnough(fromItem, toItem))
solve(data, fromItem, toItem);
else {
int middle = (fromItem + toItem) / 2;
// splitProblem(data, fromItem, toItem,
//
&middle);
divideAndConquer(data, fromItem, middle);
divideAndConquer(data, middle + 1, toItem);
combine(data, fromItem, toItem, middle);
}
}
4
DIVIDE-&-CONQUER
•
IL PARTIZIONAMENTO AVVIENE DI NORMA VERSO
PROBLEMI BILANCIATI, DI UGUALE DIMENSIONE
•
SBILANCIARE NON CONVIENE
•
SUPPONIAMO DI APPLICARE MERGESORT A 2
SOTTOPROBLEMI SBILANCIATI:
•
•
T(n) = T(1) + T(n-1) + T(merge, 1, n-1)
•
T(1) E' COSTANTE
•
T(merge, 1, n-1) E' O(n)
•
E LA COMPLESSITA' TOTALE E' O(n2)
INFATTI CON LO SBILANCIAMENTO SI E' TRASFORMATO
MERGESORT IN STRAIGHT-INSERTION!
5
DIVIDE-&-CONQUER
•
SE g(n) E' LA COMPLESSITA' DELLA SOLUZIONE DI UN
PROBLEMA smallEnough()
•
E f(n) E' LA COMPLESSITA' DI combine() 2 SOLUZIONI
PARZIALI, CIASCUNA DI DIMENSIONE n/2
•
ALLORA LA COMPLESSITA' DI divideAndConquer() E'
•
•
T(n) = g(n)
per n smallEnough()
•
T(n) = 2 * T(n/2) + f(n)
per n !smallEnough()
La complessita’ della operazione di scomposizione del
problema in due sotto-problemi (che nello schema di funzione
coincide con il calcolo di middle) e’ supposta assorbibile entro
la complessita' di combine()
6
DIVIDE-&-CONQUER
•
Vogliamo valutare il costo T(n) di risolvere un problema di
dimensione n
•
SUPPONIAMO DI DIVIDERE UN PROBLEMA DI
DIMENSIONE n IN a SOTTOPROBLEMI DI DIMENSIONE n/b
CIASCUNO
•
E CHE IL LAVORO PER OPERARE LA RICOMBINAZIONE
DELLE SOLUZIONI PARZIALI SIA c * nd
(INGLOBANDO IN QUESTO ANCHE L'EVENTUALE COSTO
DEL PARTIZIONAMENTO IN SOTTOPROBLEMI)
•
E SUPPONIAMO CHE RISOLVERE UN PROBLEMA DI
DIMENSIONE 1 ABBIA COSTO COSTANTE k1
•
ALLORA a * T(n/b) E' IL COSTO DI RISOLVERE TUTTI I
SOTTOPROBLEMI
7
DIVIDE-&-CONQUER
•
Definizione ricorsiva di T(n):
{
•
T(n)
= c * nd + a * T(n/b)
T(1)
= k1
espandiamo ricorsivamente T(n/b)
T(n) = c * nd + a * (c * (n/b)d + a * T(n/b2))
= c * nd * (1 + a/bd) + a2 * T(n/b2)
•
e continuando ad espandere ricorsivamente per p=logbn volte
T(n) = c * nd * (1 + a/bd + … + (a/bd)p-1) + ap * T(1)
•
ma ap = a logbn = (blogba ) logbn = (b logbn )logba = n logba
T(n)  k1 * n
logb a
p1
a
 c * n *  d 
j 0  b 
d
j
8
DIVIDE-&-CONQUER
•
n
n1
n
j0
j0
j0
j
j
j
n1
a
*
x

a

x
*
a
*
x

a

x
*
a
*
x

a
*
x



cioe' (se x1)
n
(1  x ) *  a * x j  a * (1  xn1)
j0
e
n1
1

x
j
a
*
x
 a*

1 x
j 0
n
9
DIVIDE-&-CONQUER
1  x n1
a

 k2
• se x<1 allora lim a *
n 
1 x
1 x
per cui k2 maggiora la sommatoria per qualsiasi n finito
•
se x=1 allora la sommatoria vale (n+1)*a
•
se x>1 per n sufficientemente grande la sommatoria e'
maggiorata da a*xn+1
10
DIVIDE-&-CONQUER
•
N.B.: la sommatoria e' quella dei primi n termini della serie
geometrica
•
La serie geometrica e la sua sommatoria
•
convergono per x < 1
•
divergono per x > 1
•
Per x = 1 la sommatoria della serie geometrica diverge
•
Per x>1 e n abbastanza grande la sommatoria della serie
geometrica coincide approssimativamente, a meno di costanti
moltiplicative, con il suo ultimo termine (o meglio, con il termine
successivo, per tenere conto dei termini precedenti)
•
N.B.: nel nostro caso x = a / bd
11
DIVIDE-&-CONQUER
 a < bd
•
Caso: x = a / bd < 1
•
T(n)  k1 * n
•
T(n)  O(n
logb a
logb a
)  O(n )
e quindi, poiche' logba < d :
•
 k2 * c * n
d
d
T(n)  O(n )
d
in questo caso domina il lavoro non ricorsivo di
ricomposizione dei risultati parziali
12
DIVIDE-&-CONQUER
 a > bd
•
Caso: x = a / bd > 1
•
T(n)  k1 * n
•
ma:
logb a
p
a
a
 d  d
b 
b 
logb n

  b


 a 
c *n * d 
b 
p
d
 a 
logb  d  
b  
logb n



T(n)  O(n
logb a


 a 
log
b d 
logb n
b 
b
 nlogb ad
)
•
e quindi:
•
in questo caso domina il lavoro ricorsivo
13
DIVIDE-&-CONQUER
 a = bd
•
Caso: x = a / bd = 1
•
T(n)  k1 * n
•
e quindi:
•
in quanto logba=d
•
in questo caso il lavoro ricorsivo e quello di
ricomposizione si bilanciano, e compare il termine
logaritmico
logb a
 c * n * logb n
d
T(n)  O(nd * logb n)
14
DIVIDE-&-CONQUER
 Riassumendo:
• se a 
bd
T(n)  O(n
• se a =
bd
T(n)  O(n * logb n)
max( d,logb a )
)
d
15
DIVIDE-&-CONQUER
 Nel caso del mergesort:
•
a=2
•
b=2
•
d=1
– quindi: a = bd
– quindi: T(n) = O(n * log2n)
 Nel caso dell’algoritmo del torneo:
•
a=2
•
b=2
•
d=0
– quindi: a > bd
log b a
– quindi: T(n) = O(n
) = O(n)
16
DIVIDE-&-CONQUER
 In generale, se
n
n
n
T(n)  a1 * T   a2 * T   ...  ak * T   c * nd
 b1 
 b2 
 bk 
allora
max( d,logb1 a1,logb 2 a2 ,...,logbk ak )
T(n)  O(n
)
salvo che le due quantita' maggiori siano uguali. In questo caso
e':
max( d,logb1 a1,logb 2 a2 ,...,logbk ak )
T(n)  O(n
* log(n))
17
DIVIDE-&-CONQUER: esempio
•
Immaginiamo di dovere individuare elemento minimo e massimo
di un vettore.
•
L'algoritmo seguente fornisce una soluzione banale del problema
typedef . . . elemento;
struct result { elemento min;
elemento max; };
struct result easyMinMax(elemento v[], int n) {
assert(n>0);
struct result res;
res.min = res.max = v[0];
for (int i=1; i<n; i+=1) {
if (v[i] < res.min) res.min = v[i];
if (v[i] > res.max) res.max = v[i];
}
return (res);
}
1
2
3
4
5
6
7
8
18
DIVIDE-&-CONQUER: esempio
•
Per analizzare la complessita' dell'algoritmo ci si concentra sul
numero di confronti tra elementi del vettore che esso esegue.
• perche' le altre operazioni sono in numero proporzionale a
questi confronti.
• perche' se gli elementi sono oggetti complessi (e.g. stringhe) il
costo di questi confronti e' predominante rispetto al costo delle
altre operazioni.
•
la complessita' di easyMinMax() e' evidentemente 2*(n-1).
•
2*(n-1) rappresenta caso migliore, peggiore, e medio.
•
e' anche immediato vedere come easyMinMax() puo' essere
migliorata:
 se v[i]<res.min non puo' essere v[i]>res.max
 quindi il secondo if (riga 6) deve essere eseguito solo se la
condizione del primo (riga 5) risulta falsa
19
DIVIDE-&-CONQUER: esempio
typedef . . . elemento;
struct result { elemento min;
elemento max; };
struct result betterMinMax(elemento v[], int n) {
assert(n>0);
struct result res;
res.min = res.max = v[0];
for (int i=1; i<n; i+=1) {
if (v[i] < res.min) res.min = v[i];
else if (v[i] > res.max) res.max = v[i];
// end if
}
return (res);
}
1
2
3
4
5
6
7
8
9
20
DIVIDE-&-CONQUER: esempio
•
la complessita' di betterMinMax() non e' piu' sempre la stessa
per i casi migliore, peggiore, e medio.
• il caso migliore si ha quando v[] e' ordinato in modo non
crescente: in questo caso il numero di confronti e' n-1.
• il caso peggiore si ha quando v[] e' ordinato in modo non
decrescente: in questo caso il numero di confronti e' 2*(n-1).
• nel caso medio sara' v[i]<res.min meta' delle volte e
quindi il numero medio di confronti sara' 3*(n-1)/2.
•
e' possibile fare "di meglio"?
•
applichiamo la strategia divide & conquer!
21
DIVIDE-&-CONQUER: esempio
typedef . . . elemento;
typedef struct result { elemento min;
elemento max; } result;
result dAndCMinMax(elemento v[],
int from, int to) {
assert(0<=from && from<= to && to<=#v);
result res;
if (to-from <= 1) {
// 1 o 2 elementi nel sottovettore
if (v[from] <=v [to]) {
res.min = v[from]; res.max = v[to];
} else {
res.min = v[to]; res.max = v[from];
}
} else {
// continua alla pagina seguente
1
2
3
4
5
6
7
8
9
22
DIVIDE-&-CONQUER: esempio
// continuazione di dAndCMinMax()
// piu' di 2 elementi nel sottovettore
int mid = (from + to) / 2;
result r1 = dAndCMinMax(v, from, mid);
result r2 = dAndCMinMax(v, mid+1, to);
res.min = (r1.min <= r2.min) ? r1.min
: r2.min;
res.max = (r1.max >= r2.max) ? r1.max
: r2.max;
}
return (res);
}
10
11
12
13
14
15
16
17
18
19
23
DIVIDE-&-CONQUER: esempio
• dAndCMinMAX() correttezza:
• per esercizio (elementare per induzione matematica).
• dAndCMinMAX() complessita':
• e' data dalla seguente relazione ricorsiva:
•
T(1) = T(2) = 1
•
T(n : n>2) = 2 * T(n/2) + 2
• T(n) = 2 * (2 * T(n/4) + 2) + 2
= 4 * (2 * T(n/8) + 2) + (4+2)
= 4 * T(n/4) + (4+2)
= 8 * T(n/8) + (8+4+2)
= ...
• e per k tale che 2k=n
T(n)  2
k 1
k 1
* T(2)   2 i  2 k 1  (2 k  2) 
i1
3*n
2
2
24
DIVIDE-&-CONQUER: esempio
•
N.B.: la complessita' calcolata per dAndCMinMAX() si applica in
tutti i casi, peggiore, migliore e medio.
•
In effetti e' dimostrabile che nessun algoritmo basato su confronti
puo' richiedere meno di 3*n/2-2 confronti.
•
Ma dAndCMinMAX() e' davvero migliore di betterMinMax()?
• in termini di complessita' spaziale e' peggiore: richiede
l'allocazione di log(n) record di attivazione ricorsiva.
• nel confronto si potrebbero contare anche le altre operazioni,
e allora il vantaggio di dAndCMinMAX() diventerebbe
minore.
• c'e' poi da considerare l'overhead temporale delle chiamate
ricorsive.
•
Cio' dimostra l'importanza, in certe circostanze, di considerare i
coefficienti moltiplicativi e i termini di grado inferiore nelle funzioni
che descrivono la complessita' degli algoritmi.
25
ALGORITMI DI ORDINAMENTO PER CONFRONTO
Algoritmo O(n2)
Corrispondente algoritmo O(n*log(n))
straight insertion

mergesort
straight selection

heapsort
bubblesort

?
•
Straight insertion si basa sulla creazione di un sottovettore localmente
ordinato e sull'inserimento in esso, uno dopo l'altro, degli elementi
restanti del vettore
•
Mergesort si basa sulla creazione di due sottovettori localmente
ordinati e sulla loro fusione ordinata
•
Straight selection, heapsort e bubblesort si basano sulla creazione di
un sottovettore globalmente ordinato e con la sua estensione
successiva con gli elementi del restante sottovettore disordinato
• N.B.: tra sottovettore ordinato e sottovettore disordinato esiste
una precisa relazione: tutti gli elementi del primo sono  di tutti gli
26
elementi del secondo
ALGORITMI DI ORDINAMENTO PER CONFRONTO
•
Straight insertion si basa
– sulla creazione di 2 sottovettori, un sottovettore localmente
ordinato e un sottovettore non ordinato (senza alcuna relazione
d’ordine tra gli elementi di un sottovettore e quelli dell’altro)
– sull'inserimento nel sottovettore ordinato, uno dopo l’altro, degli
elementi del sottovettore non ordinato
•
Mergesort si basa
– sulla creazione di 2 sottovettori, entrambi localmente ordinati
(senza alcuna relazione d’rdine tra gli elementi di un sottovettore e
quelli dell’altro)
– sul merge ordinato dei 2 sottovettori
– sull’uso della strategia Divide&Conquer
27
ALGORITMI DI ORDINAMENTO PER CONFRONTO
•
Straight selection si basa
– sulla creazione di 2 sottovettori, un sottovettore globalmente
ordinato e un sottovettore non ordinato
(gli elementi del sottovettore non ordinato sono tutti maggiori o
uguali degli elementi del sottovettore globalmente ordinato)
– sull'inserimento nel sottovettore ordinato dell’elemento minimo del
sottovettore non ordinato
•
Heapsort si basa
– sulla creazione di 2 sottovettori, un sottovettore globalmente
ordinato e un sottovettore non ordinato
(gli elementi del sottovettore non ordinato sono tutti minori o uguali
degli elementi del sottovettore globalmente ordinato)
– sul fatto che il sottovettore non ordinato e’ costituito da uno heap
basato sulla relazione “maggiore o uguale”
– sull'inserimento nel sottovettore ordinato dell’elemento massimo del
sottovettore non ordinato
28
– sull’uso della differenziazione formale
ALGORITMI DI ORDINAMENTO PER CONFRONTO
•
Straight exchange e/o bubblesort si basano
– sulla creazione di 2 sottovettori, un sottovettore globalmente
ordinato e un sottovettore non ordinato
(gli elementi del sottovettore non ordinato sono tutti maggiori o
uguali degli elementi del sottovettore globalmente ordinato)
– sull’utilizzo di una successione di scambi con elementi adiacenti del
sottovettore non ordinato per portare un elemento del sottovettore
non ordinato al proprio posto nel sottovettore ordinato
•
Quicksort si basa
– sull’applicazione della strategia Divide&Conquer
– sull’utilizzo, per spostare un elemento verso la sua posizione
corretta, di salti il piu’ lunghi possibile
29
QUICKSORT
•
•
Come saranno i due sottovettori in cui viene suddiviso il vettore da
ordinare secondo la strategia Divide&Conquer?
•
Non possono essere entrambi globalmente ordinati, altrimenti le 2
chiamate ricorsive e la funzione combine() non avrebbero niente
da fare, avrebbe fatto gia’ tutto la funzione splitProblem()!
•
Quindi almeno inizialmente non potranno essere ordinati, saranno
le chiamate ricorsive a ordinarli.
•
Ma la relazione d’ordine tra i due sottovettori?
Ma la relazione d’ordine tra i due sottovettori?
• La si conserva!
• La funzione splitProblem() dovra’ essere tale da suddividere il
vettore in 2 sottovettori tali che gli elementi dell’uno sono tutti
minori o uguali degli elementi dell’altro.
•
La funzione combine() sara’ vuota!
30
QUICKSORT
•
Quicksort si basa come bubblesort sullo scambio di elementi
disordinati.
•
Lo scambio di elementi in quicksort non ha lo scopo di mettere in
ordine elementi adiacenti.
•
Lo scambio in quicksort non avviene tra elementi adiacenti.
• Gli elementi fanno degli spostamenti maggiori: e' per questo che
ci si aspetta un comportamento migliore di quello di bubblesort
•
Lo scambio di elementi in quicksort ha lo scopo di creare due
sottovettori che abbiano la seguente proprieta':
Proprieta' P: Tutti gli elementi del primo sottovettore sono minori o
uguali di tutti gli elementi del secondo sottovettore.
•
Per ottenere un vettore ordinato e’ quindi sufficiente ordinare
localmente ciascuno dei due sottovettori ottenuti dal
partizionamento del vettore.
•
L'ordinamento dei due sottovettori e' ovviamente possibile
applicando ricorsivamente la procedura.
31
QUICKSORT
vettore v
v[0]
vettore v
v[0]
v[1]
•
i = 0..m-1: v[i]  v[m]
•
i = m+1..N-1: v[i]  v[m]
•
e quindi:
...
...
v[m]
v[N-1]
...
v[N-1]
i = 0..m-1, j = m+1..N-1 : v[i]  v[j]
•
L'operazione di suddivione del vettore nei due sottovettori separati
dall'elemento pivot m e' chiamata partizionamento
32
QUICKSORT: l’elemento pivot
•
L’elemento pivot dovrebbe essere l’elemento mediano del vettore v
•
In questo modo i due sottovettori alla sua destra e alla sua sinistra
sarebbero bilanciati
•
Ma come e’ possibile conoscere a priori quale e’ l’elemento mediano
del vettore?
•
Ci vorrebbe un oracolo.
•
In mancanza dell’oracolo ci si affida al calcolo delle probabilita’: si
utilizza come pivot un elemento a caso, il piu’ comodo, il primo
elemento del (sotto-)vettore.
33
QUICKSORT: l'algoritmo
void quicksort(int v[], int from, int to) {
if (to > from) {
int m = partition(v, from, to);
quicksort(v, from, m-1);
quicksort(v, m+1, to);
}
}
•
La funzione partition() effettua il partizionamento del vettore
v[] in due sottovettori che soddisfano la proprieta' P intorno
all'elemento pivot di indice m
•
Per ordinare il vettore int v[n] e' sufficiente chiamare
quicksort(v, 0, n-1);
34
QUICKSORT: funzione partition() .1
int partition(int v[], int from, int to) {
assert(to>from);
int pivot = v[from]; // seleziono il pivot
int fromScan = from+1;
int toScan = to;
// i=from+1..fromScan-1: v[i]v[from]
// i=toScan+1..to: v[i]v[from]
for (;;) {
while (fromScan <= toScan &&
v[fromScan] <= pivot) fromScan += 1;
while (toScan >= fromScan &&
v[toScan] >= pivot) toScan -= 1;
// continua alla pagina successiva
35
QUICKSORT: funzione partition() .2
// int partition(): continua
if (toScan > fromScan) {
int temp = v[fromScan];
v[fromScan] = v [toScan];
v[toScan] = temp;
fromScan += 1;
toScan -= 1;
} else {
break;
}
}
assert (toscan == fromscan-1);
int m = fromScan - 1;
v[from] = v[m];
v[m] = pivot;
return(m);
}
36
QUICKSORT: correttezza
.1
Teorema: La funzione partition() suddivide il sottovettore
v[from..to] in tre parti (la prima o la terza eventualmente
vuote):
•
il sottovettore v[from..m-1]
•
l'elemento v[m]
•
il sottovettore v[m+1..to]
tali che:
k = from .. m-1: v[k]  v[m]
k = m+1 .. to: v[m]  v[k]
Dimostrazione:
•
Discende immediatamente dall'invariante del ciclo esterno e dal
fatto che tale ciclo termina quando toScan=fromScan-1.
•
L'elemento v[m] al termine della funzione e' uguale all'elemento
37
v[from] all'inizio di essa.
QUICKSORT: correttezza
.2
Teorema: La funzione quicksort() ordina il sottovettore
v[from..to] in modo non decrescente.
Dimostrazione:
•
Per induzione matematica sulla lunghezza del sottovettore
v[from..to].
•
Ciascuno dei due sottovettori delle chiamate ricorsive e' lungo al
piu' to-from, per cui l'ipotesi induttiva e' applicabile.
•
Dopo le chiamate ricosive i due sottovettori sono ordinati: la
correttezza globale discende dalla correttezza della funzione
partition().
38
QUICKSORT: complessita'
.1
•
L'algoritmo quicksort ha complessita' O(n2).
•
Nel caso peggiore infatti ogni partizionamento avviene con uno dei
due sottovettori vuoto.
•
La chiamata ricorsiva e' quindi per un sottovettore di lunghezza
inferiore di un solo elemento a quella del sottovettore della
attivazione chiamante.
•
Si hanno quindi n attivazioni della funzione e ogni attivazione,
relativa ad un sottovettore di lunghezza k, effettua k-1 confronti.
•
Nel caso migliore pero' il partizionamento e’ con sottovettori
bilanciati: in questo caso l'altezza dell'albero delle chiamate
ricorsive e' solo log(n) e il comportamento dell'algoritmo diventa di
complessita' n*log(n).
•
La domanda quindi e':
• Quale e' il comportamento atteso?
• Quale e' il comportamento medio?
39
QUICKSORT: complessita' media
.2
•
L'ipotesi e' che tutte le permutazioni della sequenza di elementi da
ordinare siano equiprobabili.
•
Sia T(n) la complessita' dell'algoritmo nell'ordinamento di un
sottovettore di lunghezza n:
• T(0) = T(1) = b (costante)
• T(n) = (n - 1) + T(i-1) + T(n-i), per n  2, con i = 1..n
essendo i la posizione nel sottovettore partizionato dell'elemento
pivot.
•
Nell'ipotesi fatta i puo' assumere qualunque valore tra 1 e n con
uguale probabilita', per cui in media
1 n
T(n)  (n  1)  *  (T(i  1)  T(n  i)) 
n i1
2 n1
 (n  1)  *  T(i)
n i 0
(1)
40
QUICKSORT: complessita' media
.3
• Proviamo se la relazione e' soddisfatta da T(n) = c * n * log(n)
(che e' la complessita' "desiderata").
• Sostituiamo nella relazione ricorsiva (1):
2 * c n1
c * n * log(n)  n  1 
*   j * log( j)
n
j1
?
(2)
• Quanto vale la sommatoria che compare in (2)?
41
QUICKSORT: complessita' media
.4
• Consideriamo una generica funzione monotona crescente f(x)
n
n 1
n
 f (k )   f ( x )dx   f (k  1)
k 1
1
(3)
k 1
42
QUICKSORT: complessita' media
.5
 n

f (k  1)    f (k )   f(n  1)  f(1)

k 1
 k 1

n
Ma
per cui, sottraendo (f(n) - f(1)) dall'integrale di (3):
n 1
n
n 1
 f ( x )dx  (f (n  1)  f (1))   f (k )   f ( x )dx
k 1
1
(4)
1
consideriamo allora f(x) = x * ln(x)
tenendo conto che
x2
x2
 x  ln( x)dx  2  ln( x)  4
e sostituendo nella disequazione (4)
(vedi pagina seguente)
43
QUICKSORT: complessita' media
.6
 n2
n2  
1
 * ln( n)     0    (n  ln( n)  0)
2
 
4
4


n1
  k  ln( k ) 
k 1
 n2
n2  
1
 * ln( n)     0  
2
 
4
4


cioe'
n1
2
2
n
n
1
 k  ln( k )  2  ln( n)  4  4
k 1
44
QUICKSORT: complessita' media
.7
E dividendo per ln(2)
n1
n2
n2
1
 k  log(k )  2  log(n)  4 * ln( 2)  4 * ln( 2)
k 1
che sostituiamo nella relazione ricorsiva (2):

2  c  n2
n2
1

 n  1
   log( n) 


n
2
4
*
ln(
2
)
4
*
ln(
2
)






c
c
 * n  1 

 c * n * log( n)  1 
 2 * ln( 2) 
 2 * ln( 2) * n 
quindi, a meno di termini di ordine minore: T(n) = O(n*log(n))
45