Aldo Tragni

Gli ordini

Siano f n e g n due funzioni da ℕ → ℝ) noi diremo che:

* + =- . + f è di ordine non superiore a g (“ O: * ≤ . ”)

f n
Se esiste finito lim sup =c
9→: g n
5n= + n = O n=
5n@ + n = O n@
Esempi:
log A n = O n
n= = O n=

* + =B . + f è di ordine inferiore a g (“ o: * < . ”)

f n
Se vale che: lim =0
9→: g n
5n= + n = O n@
5n= + n = o n@
Esempi:
5n= + n = O n=
5n= + n ≠ o n=

* + =J . + f è dello stesso ordine di g (“ J: * = . ”)

f n
Se esiste finito lim
9→: g n
Alternativamente si può dire:
∃a, b > 0 nO ∈ ℕ tale che: ag n ≤f n ≤bg n ∀n > nO
=
f n = 2n + 3n + 5
Esempio: sono dello stesso ordine.
g n = n=

* + =U . + f è di ordine non inferiore a g (“ U: * ≥ . ”)

f n
Se f n ~g n cioè se: lim =1
9→: g n
f n = 2n= + 3n + 5
Esempio: f è non inferiore a g.
g n = n=
 Calcolo dei costi

Classificazione dei problemi decisionali:

- P: classe di problemi decisionali per i quali esiste un algoritmo
(deterministico) polinomiale in n (dove n è la dimensione
dell’input). Questi problemi sono anche problemi trattabili
(esempio polinomiali).
- EXP: classe di problemi decisionali risolvibili con un
algoritmo (deterministico) esponenziale.
- Intrattabili: problemi per cui esiste un algoritmo risolutivo ma
non in tempi ragionevoli.
- Decidibili: risolvibili per via algoritmica.
- NP: è la classe di problemi per cui non si conosce un algoritmo
polinomiale ma è possibile verificare in un tempo polinomiale
se una soluzione candidata è soluzione.

- Metodo dell’iterazione
Il metodo più intuitivo per risolvere una relazione di ricorrenza consiste nello “srotolare” la
ricorsione riducendola ad una sommatoria dipendente solo dalla dimensione n del problema
iniziale.
Esempio:
n
c+T se n > 1
T k = 2
1 se n = 1
Avremo:
n
T n =c+T
2
n n
T =c+T
2 4
n n
T =c+T
4 8
Quindi otteniamo:
n n n n
T n =c+T = 2c + T = 3c + T =⋯=i∙c+T `
2 4 8 2
9
Per raggiungere il costo base bisogna iterare finché non diventa a = 1 ovvero per:
=
n
= 1 → n = 2` → i = log = n volte
2`
Prendendo i = log = n si può concludere che:
n
T n = log = n ∙ c + T bcd 9 = c ∙ log n + T 1 = O log n
2 e

- Lemma fondamentale delle ricorrenza

Siano f,g due funzioni ℕ → ℕ non decrescenti. Siano n ≥ 1, v ≥ 2 due interi tali che ∀n
sufficientemente grande, valga:
n
f n ≤uf +g n u, v sono valori numerici; f in genere viene chiamata T
v
Sia: b = inf t ∶ g n = O ni
log u
Sia: a= = log j u → u = v k in qualunque base.
log v
 f n = O nk a>b Caso 1
Se a > b o
g n ≥c g n c ∈ ℝ, c ≥ 1 Condizione di Regolarità
Si ha che:
Se a < b f n =O g n Caso 2
Se a = b f n = O g n log n Caso 3

- Cambiamento di variabili
T n =T n +O 1
Questo non ricade nelle ipotesi del lemma, ma se prendo: n = 2t
u
Si ha che: T 2t = T 2 e +O 1
x
Quindi posso sostituire: R x =R +O 1
2
Utilizzando il lemma si trova che:
a = 0 b = 0 → R x = O log x
Risostituendolo: T n = T 2t = O log x
Da cui: T n = O log log n
 Algoritmi di ordinamento

-
Selection Sort (in loco)
1) Si cerca il più piccolo elemento della sottosequenza A[i…n].
2) Si scambia questo elemento con l’elemento i-esimo.
Utile quando si hanno array con chiavi molto piccole e record molto grandi perché ogni elemento
viene spostato una sola volta.
Costi:
Caso peggiore, migliore, medio: O n=

Algoritmo:
void selection(int n, int v[]) { // v = vettore da ordinare; n = lunghezza vettore
int i,j,min;

for(i=0; i<n–1; i++) {

min = i;
for(j=i+1; j<n; j++) // trova l’elemento più piccolo e ne salva l’indice in “min”
if(v[j] < v[min])
min = j;

scambia(v[min],v[i]);
}
}

- Insertion Sort (in loco)

1) Un elemento viene inserito nella posizione corretta della sottosequenza ordinata.
2) Si itera finché non rimangono elementi da inserire.
Costi:
Caso peggiore: O n= sequenza ordinata al contrario.
Caso migliore: O n sequenza già ordinata
Caso medio: O n=

Algoritmo:
void insertion_sort(int n , int v[]) {
int i, j, value;

for(i = 1; i < n; i++) {

value = v[i];
j = i – 1;
for(; (j >= 0) && (value < v[j]); j--)
v[j + 1] = v[j];
v[j+1] = value;
}
}
 - Bubble Sort (non in loco: 2n)
1) Gli elementi dell’array vengono confrontati a due a due.
2) Se l’ordine di due elementi non è corretto, essi vengono scambiati
Costi:
Caso peggiore: O n=
Caso migliore: O n
Caso medio: O n=

Algoritmo:
void BubbleSort(int n , int v[]) {
int i,alto;
for (alto = n – 1; alto > 0; alto-- )
for (i=0; i<alto; i++) {
if (v[i] > v[i+1]) // sostituire > con < per avere un ordinamento decrescente
scambia(v[i+1],v[i]);
}
}

- Merge Sort (non in loco: 2n)

1) Se la sequenza da ordinare è lunga 0 o 1 è già ordinata. Altrimenti:
2) La sequenza viene divisa in due metà.
3) Ognuna delle due sottosequenze viene ordinata iterando l’algoritmo in maniera ricorsiva.
4) Le due sottosequenze ordinate vengono fuse.
Costi:
n
T n =2T +θ n
2
Caso peggiore, migliore, medio: θ n log n

Algoritmo:
void mergesort(int array[], int i, int f) { // i = indice inizio; f = indice fine; c = indice centro
if (i<f) {
int c = (i+f)/2;
mergesort(array, i, c);
mergesort(array, c+1, f);
merge(array, i, c, f);
}
}

void merge(int array[], int left, int center, int right) {

int* temp = new int[right + 1], i,j;
for (i = center+1; i > left; i--)
temp[i-1] = array [i-1];
for (j = center; j < right; j++)
temp[right+center-j] = array [j+1];
for (int k = left; k <= right; k++)
if (temp[j] < temp[i])
array [k] = temp[j--];
else
array [k] = temp[i++];
delete [] temp;
}
 - Heap Sort (in loco)
1) Si crea un heap decrescente.
2) Per ogni iterazione, si copia la radice (primo elemento dell’array) in fondo all’array
stesso eseguendo uno scambio di elementi.
3) Viene costruito un heap di n-1 elementi eseguendo un ciclo che considera array di
dimensione progressivamente decrescente.
Costi:
Caso peggiore, migliore, medio: O n log n

- Quick Sort (in loco, divide et impera)

1) Preso un elemento come Perno, si confrontano con esso gli altri elementi e si
posizionano alla sua sinistra i minori e a destra i maggiori, senza tener conto del loro
ordine.
2) Si ricorre al quick sort per ordinare le due sottosequenze così ottenute.
Per evitare di cadere nel caso peggiore si può scegliere come Perno il mediano o si può scegliere il
Perno a caso.
Costi:
Caso peggiore: θ n=
Caso migliore: θ n log n
Caso medio: θ n log n

Algoritmo:
void quick_sort ( int Vett[] , int min , int Max ) {
int m = min, M = Max, temp, pivot = Vett[(min + Max) / 2];
while (m <= M) {
while (Vett[m] < pivot)
m++;
while (Vett[M] > pivot)
M--;
if (m <= M) {
scambia(Vett[m], Vett[M]);
m++;
M--;
}
};
if (min < M)
QS (Vett, min, M);
if (m < Max)
QS (Vett, m, Max);
}

- Counting Sort (non in loco)

1) L’algoritmo conta il numero di occorrenze di ciascun valore presente nell’array da
ordinare, memorizzando quest’informazione in un array temporaneo pari all’intervallo
dei valori.
2) Si calcolano i valori massimo e minimo dell’array e si prepara un array ausiliario C di
dimensione pari all’intervallo dei valori, con C[i] che rappresenta la frequenza
dell’elemento i+min(A) dell’array di partenza.
 3) Si visita l’array aumentando l’elemento di C corrispondente. Dopo si visita l’array in
ordine e si scrivono su A c[i] copie del valore i+min(A).
Costi:
k = max A − min A + 1
Caso peggiore: O n + k
Caso migliore: O n + k
Caso medio: O n + k

Algoritmo:
a = vettore di interi da ordinare
c = vettore intermedio
b = vettore finale in cui inserirò gli elementi ordinati
for( i=0; i<k; i++ ) c[i]=0; // azzero vettore intermedio
for( i=0; i<n; i++ ) c[ a[i] ]++; // conto le occorrenze dei valori di a
for( i=1; i<k; i++ ) c[j] = c[j–1] + c[j];

for( i=n–1; i>=0; i-- ) {

c[ a[i] ]--;
b[ c[ a[i] ] ];
}

- Radix Sort
Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno significativa.
Questo affinché l’algoritmo non si trovi a dover operare ricorsivamente su sottoproblemi
non valutabili a priori.
Costi:
N: lunghezza dell′array
Caso peggiore: O kN
k: media del numero di cifre degli n numeri

Algoritmo:
d = numero di cifre del valore massimo (se ho: 1,20,400 allora d=3 e i numeri verranno
considerati così: 001, 020, 400).
Si ordinano i valori partendo dalla cifra di destra.
for( i=0; i<d; i++ ) // i = 0 indica la cifra più a destra del valore
“uso un algoritmo stabile (in genere il Bucket Sort) per ordinare l’array rispetto alla i-esima cifra”

- Bucket Sort
1) L’intervallo dei valori, noto a priori, è diviso nel bucket a cui appartiene.
2) Ciascun valore dell’array viene inserito nel bucket a cui appartiene.
3) I valori all’interno dei bucket vengono ordinati.
4) Vengono concatenati i valori contenuti nei bucket.
Caso peggiore: O n log n
Caso migliore: O n se gli elementi nei bucket sono uniformemente distribuiti.
 Strutture dati

- Lista
Il nome della lista corrisponde a un indirizzo di memoria che contiene l’indice al primo elemento.
Ogni elemento contiene anche l’indice all’elemento successivo.
L’inserzione in testa costa O 1 , poiché sono all’inizio.
L’inserzione in una posizione i costa O i , perché devo trovarla.
Stessa cosa per la cancellazione.

- Pila
Realizzabile con una lista in cui:
- Push: inserisce in testa alla lista.
- Pop: elimina l’elemento in testa alla lista.
- Top: legge l’elemento in testa.
Tutte costo O 1
Segue la politica LIFO (last input first output): l’ultimo inserito è il primo ad essere tolto.

Posso farla anche con un array (inserisco gli elementi a partire dalla prima posizione dell’array;
quando inserisco devo controllare che ci si spazio nell’array; quando tolgo devo controllare che ci
sia qualcosa da togliere; avrò bisogno di un N che indica quanti elementi ho inserito nell’array).

- Coda
Realizzabile con una lista in cui:
- enqueue: inserire in coda.
- dequeue: rimuove un elemento dalla testa della coda.
Tutte costo O 1
Segue la politica FIFO (first input first output): il primo ad essere inserito è il primo ad essere tolto .

Si può fare anche con un array circolari:

0 Testa della coda
a0
1
a1
a2
2
a3
Coda della coda
3
 - Albero Binario
E’ una struttura definita su un insieme finito di nodi tale che o è un insieme vuoto o è composto da
tre insiemi distinti, che sono:
1) Un nodo
2) Un sottoalbero sinistro
3) Un sottoalbero destro
La dimensione di un albero è il numero di nodi contenuti nell’albero.
La profondità di un nodo è la distanza, in termini del numero di archi, del cammino radice-nodo. La
profondità della radice è zero, quella dei figli della radice è 1, …
L’altezza di un albero è la massimo profondità delle sue foglie, è cioè la profondità del cammino
più lungo.

- Albero binario perfettamente bilanciato: è un albero i cui nodi interni hanno esattamente 2 figli e
tutte le fogli sono allo stesso livello.

k=3

- Albero binario quasi perfettamente bilanciato: è un albero di altezza k che è perfettamente

bilanciato fino al livello k-1

k-1 = 2

k=3

- Heap
Proprietà di Struttura: il MaxHeap è un albero binario quasi perfettamente bilanciato con i nodi
all’ultimo livello addossati a sinistra.
Questa proprietà permette di inserire un albero binario in un array.
Proprietà di Valore: in ogni sottoalbero di un MaxHeap, la radice contiene un valore maggiore di
entrambi i valori dei figli (minore nel caso si parli di MinHeap).

Nel MaxHeap, dalla proprietà di valore, segue che nella radice si trova il valore massimo:
20

17 13

5 15 9 11

3 2 4 10 1 8
Posso memorizzarlo in un array leggendolo ad ogni livello, da sinistra a destra:
20 17 13 5 15 9 11 3 2 4 10 1 8
Proprietà 1):
` @
Il nodo in posizione i con i > 1 ha per padre il nodo in posizione (es. = 1).
= =
Gli indici i partono da 1 e non da 0 come negli array; i=1 indica il nodo in array[0] .
Per il motivo indicato sopra, nell’array contenente l’heap si parte ad inserire dalla posizione 1.
Proprietà 2):
Il nodo in posizione i se ha figli, li ha in posizione 2 ∗ i e 2 ∗ i + 1 (figlio sinistro e figlio
destro).
Proprietà 3):
Dato un heap di n nodi:
n
#nodi interni = nodi che hanno almeno un figlio
2
n
#foglie =
2
Altezza albero: h = θ log n

Codice:
// h.v = vettore dell’heap; h.n = elementi contenuti nel vettore (non la lunghezza del vettore)
fixup( int k, heap& h ) {
while( k>1 && h.v[k/2]<h.v[k] ) {
scambia( k, k/2, h );
k = k/2;
}
}
- Se la applico ad un elemento appena inserito (in fondo al vettore), essa sistema tale elemento
nell’MaxHeap (se si vuole convertire un vettore in un MaxHeap, si inserisce un elemento alla volta,
applicando questa funzione).

void fixdown( int k, heap &h ) {

j = 2*k; //posizione del figlio sinistro
if( j<=h.n ) { //se ha almeno un figlio
if( j<h.n && h.v[j]<h.v[j+1] ) j++;
if( h.v[k]<h.v[j] ) {
scambia( k,j,h );
fixdown( j,h );
}
}
}
Se non sono arrivato all’ultimo elemento del vettore (cioè, se il figlio esiste)…
Se il figlio sinistro è più piccolo del figlio destro…
Se il padre e minore del maggiore fra i due figli, li scambio e ripeto la fixdown…
9
Questa procedura fixdown ha costo O log .
A
- Quando cancello un elemento, sposto l’ultimo elemento dell’heap nella posizione dove ho
cancellato e applico questa funzione.

void buildheap( heap &h ) {

for( j = (h.n)/2; j>=1; j-- )
fixdown( j,h );
}
- Applicata ad un vettore, lo trasforma in un MaxHeap.
Costa O n .
 - Tabella Hash

- Alberi:
- Alberi ordinali e binari:
- Alberi binari di ricerca (anche bilanciati):

- Grafi (con viste di grafi DFS e BFS):

- Alberi AVL:

- Programmazione dinamica:

- Skiplist (con ricerca):

- Skiplist – liste a salti:
- Backtracking:

Ricerche:
- Visita posticipata: è una visita dell’albero in cui prima si visita il sottoalbero sinistro, poi il destro
e infine la radice.

Ricerca sequenziale:

Ricerca binaria (in vettore ordinato):

Ricerca binaria (in albero binario):

Ricerca proporzionale:

Ricerca a salti:

Ricerca proporzionale e a salti combinate:

Ordinamenti:
- Stabile: un algoritmo di ordinamento è stabile se dato un array in cui ci sono più chiavi uguali,
dopo aver applicato l’algoritmo, esse mantengono lo stesso ordinamento relativo.
Merge Sort: è stabile.