Appunti di algoritmi e strutture dati

CASO MEDIO

Dobbiamo far riferimento al caso medio per poter valutare le prestazioni di questo algoritmo. Le situazioni 'favorevoli' risultano essere 'molte' mentre quelle 'sfavorevoli' risultano essere 'poche'. Per capire il perché, andiamo ad analizzare due casi in cui c'è un pessimo bilanciamento:

1. Partizionamento sbilanciato

   Supponiamo che ad ogni chiamata, la procedura Partiziona produca una partizione che è i 9/10 dell'altra. L'equazione di ricorrenza diventa:

   T(n) = T(9n/10) + T(n/10) + n

   Se andassimo ad analizzare l'albero di ricorsione, visto che il rapporto 9/10 è costante ad ogni livello di ricorsione, otterremmo che la ricorsione termina alla profondità:

   Quindi il costo totale del QuickSort sarebbe proprio Θ(n log n).

2. Partizionamento molto sbilanciato

   Supponiamo che ad ogni chiamata,

Appunti a cura di Liccardo Giuseppe - Università degli Studi di Napoli Parthenope

Pagina | 20

La procedura Partiziona produce una partizione che è i 99/100 dell'altra. L'equazione di ricorrenza diventa: T(n) = T(99n/100) + T(n/100) + n.

Se andassimo ad analizzare l'albero di ricorsione, visto che il rapporto 99/100 è costante ad ogni livello di ricorsione, otterremmo che la ricorsione termina alla profondità:

Quindi il costo totale del QuickSort sarebbe proprio Θ(n log n). La ragione è che qualsiasi ripartizione con proporzionalità costante produce un albero di ricorsione di profondità Θ(log n), dove il costo in ogni livello è O(n).

Proprio per l'alta probabilità di ricadere in un caso favorevole piuttosto che in un caso sfavorevole, il pivot viene scelto in modo casuale tra gli indici del vettore, cioè ogni elemento del vettore ha una probabilità pari a 1/n di essere selezionato come pivot. Utilizzando questo metodo, risulta altamente improbabile ricadere nel caso peggiore.

elemento ha una probabilità di essere estratto pari a 1/n, otteniamo:

Scomponendo otteniamo:

Risolvendo quest’ultima ricorrenza con il metodo di sostituzione, otteniamo:

2.4 Albero di decisione

Gli algoritmi di ordinamento visti finora sono degli algoritmi di ordinamento basati su confronti tra gli elementi di input, cioè algoritmi in cui si usano soltanto i confronti tra gli elementi per determinare l’ordine degli stessi. Ciò comporta che la loro complessità minore sia Ω(n log n).

Andremo a dimostrare che ogni algoritmo di ordinamento basato su confronti deve eseguire Ω(n log n) confronti per ordinare un array di n elementi. Per fare ciò, supporremo che tutti gli elementi di input siano distinti. Per questa ipotesi, saranno superflui confronti del tipo a = a e saranno equivalenti ii j confronti a ≤ a , a ≥ a , a < a e a > a ; tutti questi confronti saranno indicati con la forma a ≤ a .

2.4.1 Il modello

Gli ordinamenti per confronti possono essere rappresentati in maniera astratta mediante gli alberi di decisione. Un albero di decisione è un albero binario completo che rappresenta i confronti tra elementi che vengono effettuati da un algoritmo di ordinamento. Tutti gli altri aspetti dell'algoritmo, come lo spostamento dei dati, vengono ignorati.

In un albero di decisione:

• la radice è etichettata con la sequenza in input <a , a , < , a >
• le foglie sono etichettate con la sequenza risultato
• i nodi interni sono etichettati con i confronti tra elementi della sequenza
• gli archi rappresentano le operazioni che vengono eseguite tra un confronto e il successivo

Quindi, i cammini dalla radice alle foglie rappresentano le sequenze di operazioni che l'algoritmo effettua per ordinare l'array. Tali sequenze di

Le operazioni si differenziano in corrispondenza dei confronti che vengono effettuati. Inoltre, bisogna sottolineare che un nodo etichettato "i : j" specifica un confronto tra gli elementi K e Ki j secondo la loro posizione nell'array iniziale e non nella loro posizione corrente.

Di seguito riportiamo altre caratteristiche degli alberi di decisione:

• Siccome le permutazioni di 1, 2, <, n sono n!, ciò implica che l'albero di decisione deve avere almeno n! foglie.
• L'altezza dell'albero di decisione (il più lungo percorso radice-foglia) corrisponde al numero di confronti che l'algoritmo esegue per ordinare nel caso peggiore.
• Visto che un albero binario con N foglie deve avere altezza almeno pari a log(N) [segue dimostrazione], allora l'algoritmo deve eseguire almeno log(n!) confronti.

DIMOSTRAZIONE

Il grado di un nodo è dato dal numero di figli del nodo stesso. In un albero binario, ogni nodo può avere al più due figli.

quindi il grado di ciascun nodo può essere 0, 1 o 2.

LEMMA 1

Per un qualsiasi albero binario non vuoto, se:

• F è il numero di foglie
• M è il numero di nodi di grado 2 (aventi due figli)

Vale che:

F = M + 1

Dimostrazione Lemma 1:

Siano:

• K il numero di nodi di grado 1
• N il numero totale di nodi dell'albero

Vale che:

N = F + M + K (1)

Se B è il numero dei rami, allora N = B + 1 perché ogni nodo ha un ramo entrante tranne la radice.

Siccome tutti i rami escono da nodi di grado 1 o di grado 2, allora B = K + 2M

Segue che:

N = B + 1 = K + 2M + 1 (2)

Dalla (1) e dalla (2) si ottiene:

LEMMA 2 - 3

In un albero binario:

1. il massimo numero di nodi al livello i è 2^i-1, con i ≥ 1
2. il massimo numero di nodi di un albero di profondità k è 2^k - 1, con k ≥ 1

COROLLARIO

Sia F il numero di foglie di un albero binario, allora la minima profondità dell'albero è log₂F

Appunti a cura di Liccardo Giuseppe

Università degli Studi di Napoli Parthenope

Pagina | 23

Dimostrazione Corollario:

Dal lemma 1 e dal lemma 3 otteniamo:

N = F + M + K = 2 - 1k

N = F ≤ 2 - 1k

N = k ≥ log F2

Sia h l'altezza dell'albero di decisione. Poiché l'albero è binario, sappiamo dal Corollario precedente che:

h ≥ log(n!)

Quindi:

2.5 Algoritmi di ordinamento non basati sui confronti

Ora esamineremo tre algoritmi di ordinamento - CountingSort, RadixSort e BucketSort - che riescono ad ordinare una sequenza di input usando operazioni diverse dai confronti, di conseguenza, il limite inferiore Ω(n log n) non può essere applicato a questi algoritmi.

2.5.1 Algoritmo CountingSort

L'algoritmo CountingSort suppone che ciascuno degli n elementi di input sia un numero intero compreso nell'intervallo *0, k].

Supponiamo di voler ordinare l'array A[1..n].

Occorrono altri due array:

- un array B[1..n] che conterrà l'output

ordinato- un array C[0..k] che verrà utilizzato come array di appoggio, cioè come area di lavoro

FUNZIONAMENTO

L'array A di input è il seguente:

Costruisco la prima versione dell'array C, la cui dimensione sarà data dalla distanza 0..k. Gli elementi dell'array A vanno da 0 a 4, quindi la distanza è 5, che sarà proprio la dimensione dell'array C.

Nell'array C, per ogni indice metto il numero di presenze che riscontro nell'array A:

- l'elemento 0 è presente due volte C[0] = 2

- l'elemento 1 è presente due volte C[1] = 2

- l'elemento 2 è presente tre volte C[2] = 3

- l'elemento 3 non è presente C[3] = 0

- l'elemento 4 è presente una volta C[4] = 1

Costruisco ora la seconda versione dell'array C, inserendo al suo interno una sorta di 'somma incrementale':

- nel primo elemento lascio il valore già presente al suo interno

1. nel secondo elemento ci metto la somma degli elementi di posto 0 e 1 C[1] = 2+2 = 4
2. nel terzo elemento ci metto la somma degli elementi di posto 1 e 2 C[2] = 4+3 = 7
3. nel quarto elemento ci metto la somma degli elementi di posto 2 e 3 C[3] = 7+0 = 7
4. nel quinto elemento ci metto la somma degli elementi di posto 3 e 4 C[4] = 7+1 = 8

Appunti a cura di Liccardo Giuseppe – Università degli Studi di Napoli Parthenope

A questo punto, l'array C conterrà gli indici dove andranno posti gli elementi dell'array di input A.

È possibile ora costruire l'array ordinato di output B.

Si scorre l'array A a partire dall'ultimo elemento fino ad arrivare al primo. In base al valore dell'array A si va a selezionare dall'array C la posizione che andrà ad occupare quell'elemento nell'array B. Ad ogni passo si decrementa il valore dell'indice 'utilizzato' nell'array C.

Il valore

1. di A[8] è 2. Si considera C[2], il cui valore è 7. Si assegna a B[7] il valore 2. Si decrementa C[2] che passa da 7 a 6. Il valore di A[7] è 0. Si considera C[0], il cui valore è 0. Si assegna a B[2] il valore 0. Si decrementa C[0] che passa da 2 a 1. Il valore di A[6] è 2. Si considera C[2], il cui valore è 6. Si assegna a B[6] il valore 2. Si decrementa C[2] che passa da 6 a 5. E così via fino al primo elemento dell'array A.
2. Il valore di A[1] è 1. Si considera C[1], il cui valore è 3. Si assegna a B[3] il valore 1. Si decrementa C[1] che passa da 3 a 2. Come si può vedere, l'array B risulta ordinato.
3. 2.5.2 Pseudocodice CountingSort