Array e riferimenti
• Consideriamo la seguente definizione:
int v[10];
il compilatore alloca nella memoria uno spazio per 10 componenti intere e mette nella variabile v l’indirizzo di memoria di v[0].
Pertanto v è un puntatore ad un’area di tipo intero.
v[0] v[9]
v
Array e riferimenti
• La variabile v contiene il valore &v[0].
• Possiamo accedere a v[0] non solo tramite l’indice ma anche considerando il contenuto di v: *v.
• Quando un array è variabile di scambio in un sottoprogramma, viene passato il valore presente nella variabile v: è per questo che le componenti dell’array sono visibili anche al sottoprogramma.
• Come parametro formale si può usare, oltre a int v[] anche int * .
Aritmetica dei puntatori
• Nel linguaggio C++ è possibile accedere ad aree di memoria successive a quelle memorizzate in un puntatore. Consideriamo
int *p;
p = …;
p = p+1;
• Dopo l’assegnazione pvede l’area successiva. p
Aritmetica dei puntatori
• In generale si ha:
p = p + n;
l’indirizzo iniziale di p viene incrementato di un numero di byte uguale a:
n*(n° byte dell’area puntata da p)
• Esempio.
short *p;
p = &varintera;
p = p+2; p
Aritmetica dei puntatori
• L’indirizzo contenuto in p viene incrementato di 2*(2 byte) = 4 byte.
• Esempio.
double *q;
q = &vareale;
q = q+3;
• L’indirizzo contenuto in q viene incrementato di 3*(8byte) = 24 byte.
Aritmetica dei puntatori
• Possiamo anche usare l’aritmetica dei puntatori per accedere alle componenti di un array: dal momento che v contiene &v[0] e che *v coincide con v[0], abbiamo che:
*(v+1) coincide con v[1]
*(v+2) coincide con v[2]
. . .
• Invece di accedere alle componenti tramite un indice si può accedere anche tramite un indirizzo di memoria (non useremo questa tecnica).
Costruzione di una lista concatenata: inserimento in testa
• Definizione del nodo:
struct tipolista{
int dato;
tipolista *punt;
};
tipolista *p, *inizio;
• Costruzione della lista.
• Si parte da lista vuota:
inizio = NULL; ••••
inizio
Costruzione di una lista concatenata: inserimento in testa
• Si aggiunge il primo elemento:
p = new tipolista;
p->dato = 1;
p->punt = inizio; //NULL inizio = p;
1 ••••
inizio
p
Costruzione di una lista concatenata: inserimento in testa
• Costruzione degli altri elementi: inserimento in testa:
p = new tipolista;
p->dato = 5;
p->punt = inizio;
inizio = p;
5
••••
1 inizio
p
Costruzione di una lista concatenata: inserimento in testa
• Quando si costruisce una lista inserendo tutti gli elementi in testa, le istruzioni sono le stesse per il primo e per tutti gli altri elementi.
• Si ha quindi una struttura iterativa che termina quando si inserisce l’ultimo elemento: poiché la lista concatenata non possiede un numero prefissato di elementi, si può avere una condizione con un controllo su un valore speciale oppure una scelta per continuare o no.
Costruzione di una lista concatenata: inserimento in coda
• Per inserire un elemento alla fine della lista, in coda, è necessario avere un puntatore che contiene il riferimento all’ultimo elemento
tipolista *p, *inizio, *ultimo;
• Costruzione della lista.
• Si parte da lista vuota:
inizio = NULL; ••••
inizio
Costruzione di una lista concatenata: inserimento in coda
• Si aggiunge il primo elemento:
p = new tipolista;
p->dato = 1;
p->punt = NULL; //il primo è anche
inizio = p; //l’ultimo
ultimo = p;
1 ••••
inizio
p ultimo
Costruzione di una lista concatenata: inserimento in coda
• Costruzione degli altri elementi:
inserimento in coda:
p = new tipolista;
p->dato = 5;
p->punt = NULL;
ultimo->punt = p;
ultimo = p; 5
1
••••
inizio
ultimo p
Costruzione di una lista concatenata: inserimento in coda
• Quando si costruisce una lista inserendo tutti gli elementi in coda, le istruzioni per inserire il primosono diverse da quelle per inserire tutti gli altri elementi.
• Il primo elemento si aggancia a inizio inizio = p;
gli altri si agganciano a ultimo->punt ultimo->punt = p; .
Inserimento e cancellazione in una lista concatenata
• Per poter inserire o cancellare un elemento in una lista occorre trovare il punto in cui eseguire l’operazione: occorre pertanto eseguire una scansione lineare della lista con un puntatore pos di tipo tipolista.
• Questa scansione lineare si fa cercando un elemento della lista: si può inserire prima o dopo l’elemento (se è presente), si può cancellare l’elemento successivo, il precedenteo l’elemento stesso.
Ricerca in una lista concatenata
• Si cerca un elemento elem a partire dall’inizio della lista:
pos = inizio;
trovato = false;
while((pos!=NULL) && (!trovato)){
if(pos->dato == elem) trovato = true;
else pos = pos->punt;
}//ricerca lineare
Inserimento in una lista concatenata
• Caso 1. Inserimento (di 1) dopo un elemento presente (6): p->punt=pos->punt;
pos->punt =p;
1 inizio
p
••••
2 6 3
pos
Inserimento in una lista concatenata
• Caso 2. Inserimento prima di un elemento presente.
• Per eseguire questo inserimento si deve eseguire la scansione con due puntatori: pos
“cerca” l’elemento, prec “vede” il precedente.
inizio
prec
••••
2
pos 6
Inserimento in una lista concatenata
• Scansione con due puntatori:
while((pos!=NULL) && (!trovato)){
if(pos->dato == elem) trovato = true;
else {prec = pos;
pos = pos->punt;}
}
• L’inserimento viene effettuato dopo l’elemento (2) “visto” da prec.
Cancellazione in una lista concatenata
• Caso 1. Cancellazione dopo un elemento.
• Si può eseguire la cancellazione dopo solo se l’elemento trovato non è l’ultimo.
if(pos->punt != NULL)
pos->punt = pos->punt->punt;
• Caso 2. Cancellazione dell’elemento trovato.
• Si esegue la scansione con due puntatori e si cancella dopo prec; se l’elemento trovato è il primo della lista (se pos == inizio) allora si deve modificare il valore di inizio.
Cancellazione in una lista concatenata
• Caso 3. Cancellazione prima di un elemento.
• Si esegue la scansione con due puntatori, si scambiano i campi dato (scambiare 2 con 6) dei due riferimenti visti da prec e pos e si effettua la cancellazione dopo prec .
• Altre operazioni: costruire una lista ordinata, inserire un elemento in ordine, eseguire la fusione di due liste ordinate, . . .
Primo e ultimo elemento in una lista concatenata
• Nelle operazioni di inserimento e cancellazione si deve prestare molta attenzione al primo e all’ultimo elemento:
• il primo elemento è individuato dal puntatore inizio, quindi:
pos == inizio
• l’ultimo elemento contiene il riferimento NULL, quindi:
pos->punt == NULL
Allocazione statica e dinamica
• Si parla di allocazione statica quando lo spazio per le variabili viene riservato prima dell’inizio dell’esecuzione del programma: lo spazio viene allocato durante la compilazione.
• Si parla di allocazione dinamica quando lo spazio per le variabili (alcune) viene riservato durante l’esecuzione del programma.
• L’allocazione dinamica si ha utilizzando l’operatore new.
(par. 11.4)
Allocazione statica e dinamica
• Le variabili allocate dinamicamente restano accessibili anche quando il sottoprogramma è terminato: abbiamo visto la costruzione di una lista concatenata in un sottoprogramma e la stampa di tale lista in un sottoprogramma diverso.
• Le variabili allocate dinamicamente occupano una parte della memoria che si chiama Heap.
• Le variabili allocate staticamente occupano una parte di memoria chiamata Stack.
Allocazione statica e dinamica
• Cosa accade delle variabili che non sono più referenziate? Quando si cancella un elemento da una lista, quell’area allocata non è più visibile poiché non c’è un puntatore che permette di accedervi. Come si può riutilizzare?
• Nei linguaggi che utilizzano molta allocazione dinamica, come Java, esiste un programma per la “ripulitura” automatica della memoria:
garbage collector.
Allocazione statica e dinamica
• Il garbage collector scandisce la memoria e marca le aree non più referenziate e le rende nuovamente libere.
• Nel linguaggio C++ (Pascal) si deve eseguire una ripulitura manuale della memoria utilizzando l’istruzione delete.
• Per usare correttamente tale istruzione si deve conoscere con esattezza quale area vuole cancellare (non tratteremo questo argomento).
TDA: Tipo di dati Astratto
TDA: Tipo di dati Astratto
• Si vuole costruire un nuovo tipo di dato: si deve quindi definire un dominio (i dati) e le funzioni che operano sul dominio (le operazioni che possiamo fare sugli elementi del dominio).
• I tipi di dato astratto (ADT: Abstract Data Type) che consideriamo sono dei contenitori di informazioni e si differenziano per le operazioni che possono essere eseguite su quelle informazioni: pila, coda, lista, dizionario, albero.
TDA: Tipo di dati Astratto
• Una volta stabilito cosa può fare il TDA, dobbiamo realizzarlo e scegliere come vengono effettuate le operazioni: dobbiamo scegliereuna struttura di dati.
• Una struttura di dati è un modo di organizzare dati ed è caratterizzata da una sua propria modalità di accesso.
• Le strutture di dati che abbiamo visto sono:
arraye liste concatenate.
TDA: Tipo di dati Astratto
• Poiché un TDA rappresenta in generale un contenitore di informazioni, le funzioni che operano sul dominio dovranno svolgere:
• inserimento di un elemento
• rimozione di un elemento
• ispezione degli elementi contenuti nella struttura:
ricercadi un elemento all’interno della struttura
• Ci sono delle operazioni che si fanno in maniera efficiente sia con array che con lista concatenata, altre risultano più complesse con una struttura piuttosto che con l’altra.
Pila o Stack
Pila o Stack
• Una Pila è un TDA ad accesso limitato.
• Si può accedere solo al primo elemento della Pila, detto anche testa.
• Le sue funzioni sono:
• verifica se la Pila è vuota: isEmpty
• guarda la testa: top
• inserisci in testa: push
• estrai la testa: pop
Pila o Stack
• In una Pila gli oggetti possono essere inseriti ed estratti secondo un comportamento definito LIFO:
Last In First Out
l’ultimo inserito è il primo a uscire
Il nome ricorda una “pila di piatti”:
l’unico oggetto che può essere ispezionato è quello che si trova in cima alla pila.
Pila o Stack
• Le operazioni che caratterizzano questo TDA non sono tutte sempre possibili; possiamo sempre aggiungere un elemento in cima alla Pila, ma se la Pila è vuota:
• non possiamo togliere la testa della Pila
• non possiamo ispezionare la testa della Pila.
• Vediamo come si realizza una Pila mediante la struttura di dati array e poi mediante la lista concatenata.
Pila o Stack
• Supponiamo di rappresentare una Pila con un array di interi di 5 componenti:
int vett[5];
• Per realizzare il TDA Pila dobbiamo:
• rappresentare la situazione Pila vuota
• per poter inserire un elemento, sapere quale è la prima posizione libera
• Utilizziamo una variabile intera il cui valore indica la prima posizione libera: sp (stack pointer) .
Pila o Stack
int sp;
• Pila vuota:
sp = 0;
• inserire in testa:
vett[sp] = valore;
sp++;
• accedere alla testa:
vett[sp-1]
• estrarre la testa sp--;
4 3 2 1 0
Pila o Stack
• Esempio:
• si parte da Pila vuota: sp=0
• inseriamo in testa il valore 6:
vett[sp]=6; 4
sp++; // sp=1 3
• inseriamo in testa 15: sp = 2
vett[sp]=15; sp = 1
sp++; // sp=2 sp = 0 6
15
Pila o Stack
• guardiamo la testa:
accesso all’elemento vett[sp-1] // 15
• togliamo la testa:
sp--; // sp=1 l’elemento non viene cancellato, ma 15 non è più accessibile
6 15 4 3 2 sp=1 sp=0
Pila o Stack
• Utilizzodi una Pila.
• Durante l’esecuzione di un programma nel RuntimeStack sono allocate aree per i descrittori dello stato dei sottoprogrammi che sono sospesi.
• Un editor mantiene traccia delle operazioni eseguite: quando si effettua un “undo” per annullare un’operazione, si eliminano le ultime eseguite ripristinando lo stato precedente:
l’ultima modifica viene eliminata “estraendola”
dalla testa della pila.
Operazioni su una Pila
Stampare una Pila
• Quando si stampa un Pila gli elementi appaiono nell’ordine inverso a quello di inserimento; inoltre la Pila si vuota.
• Supponiamo di avere introdotto nella Pila i valori 1, 2, 3 nell’ordine; per stampare la Pila bisogna accedere ad ogni elemento e poiché è accessibile solo la testa, per poter “vedere” gli altri elementi si deve togliere la testa. Poiché la testa è l’ultimo elemento inserito, gli elementi appaiono in ordine inverso.
Stampare una Pila
1 3 2
stampa testa stampa testa stampa testa
3 2 1
• Se vogliamo stampare gli elementi nello stesso ordine di inserimento, dobbiamo prendere un’altra Pila e “rovesciare” quella iniziale e stampare la nuova Pila.
1 1
2
Pila vuota
Stampare una Pila
1 3 2
1
1
2
3
3 2
3 2 1 Nuova Pila
Nuova Pila
Ricerca in una Pila
• Non ci sono assiomidi “ricerca elemento” tra gli assiomi dello Stack.
• Pertanto se vogliamo eseguire la ricerca di un elemento in una Pila è necessario utilizzare una Pila di appoggio ed estrarre gli elementi dalla Pila in cui eseguire la ricerca. Se la testa coincide con l’elemento cercato allora l’elemento è presente. Se la Pila iniziale si vuota l’elemento non è presente.
• Successivamente si reinseriscono nella Pila iniziale gli elementi tolti.
Pila o Stack
• Esercizio. Si consideri una formula matematica; scrivere un algoritmo per verificare se le parentesi sono o no bilanciate.
• Analisidel problema.
• La formula
{a + (b-c) * [(a + b) - 7]}
ha parentesi bilanciate, mentre la formula {a + (b-c}-5)
non ha parentesi bilanciate, anche se il numero di tonde e graffe aperte coincide con il numero di quelle chiuse. Quindi non è sufficiente contarle.
Pila o Stack
• Se vogliamo realizzare il TDA Pila con una lista concatenata: dovremo realizzare gli assiomi:
• verifica se la Pila è vuota
• guarda la testa
• inserisci in testa
• estrai la testa
• Possiamo costruire delle funzioni che rappresentano le varie operazioni.
Pila o Stack
• Abbiamo visto la costruzione di una lista concatenata con inserimento in testa.
• Se vogliamo realizzare il TDA Pila, Stack, dobbiamo costruire della funzioni che rappresentano gli assiomi:
• inserire in testa un nuovo elemento: push
• estrarre dalla testa il primo elemento: pop
• ispezionarela testa: top
• verificarese lo Stack è vuoto: isEmpty
Realizzare una Pila, Stack
• La realizzazione della funzioni può utilizzare l’array o la lista concatenata.
• Il programma che costruisce la Pila, utilizzerà una struttura iterativa che chiama una funzione
“inserisciintesta” (push) senza “sapere” quale è la struttura di dati utilizzata.
• Il programma che gestisce la Pila avrà delle funzioni per: estrarre il primo elemento (pop), restituire il valore del primo elemento (top) e verificare se la Pila è vuota oppure no (isEmpty).
Realizzare una Pila, Stack
• Pertanto un programma per gestire il TDA Pilasarà del tipo:
• costruzionedella Pila
finché ci sono dati da inserire chiama inserisciintesta
• stampadella Pila:
finché la Pila non è vuota chiama stampa la testa chiama estrai la testa
Complessità delle funzioni della Pila
• Vogliamo calcolare la complessità delle operazioni che riguardano la realizzazione degli assiomi della Pila.
• La complessità delle operazioni dipende dalla struttura di datie non dal TDA.
• Le operazioni sono: isEmpty, push, pop, top.
Complessità delle funzioni della Pila
• Il tempo di esecuzione di ogni operazione su una Pila realizzata con array (di dimensione compatibile) è costante: abbiamo solo un numero costante di assegnazioni, confronti o restituzione di valore. Il tempo non dipende dalla dimensione della struttura dati: quindi O(1).
• Anche per la lista concatenata si ha un numero costante di assegnazioni sui puntatori, confronti, restituzione di valore: quindi O(1).
Coda o Queue
Coda o Queue
• Una Coda è un TDA ad accesso limitato.
• Si può accedere al primo elemento della Coda, detto testa e all’ultimo elemento detto coda.
• Le sue funzioni sono:
• verifica se la coda è vuota: isEmpty
• guarda la testa: front
• inserisci in coda: enqueue
• estrai la testa: dequeue
Coda o Queue
• In una Coda gli oggetti possono essere inseriti ed estratti secondo un comportamento definito FIFO:
First In First Out
il primo inserito è il primo a uscire
Il nome ricorda una “fila in attesa”: viene estratto l’elemento che si trova
“in coda” da più tempo, testa.
Coda o Queue
• Gli assiomi assomigliano a quelli della Pila:
• verifica se la Coda è vuota: isEmpty
• guarda la testa: top, front
• estrai un elemento (la testa): pop, dequeue
• inserisci un elemento: push (testa), enqueue (coda)
• Solo l’inserimento è diverso: nella Pila si inserisce in testa, nella Coda alla fine.
• La Coda si può realizzare su array oppure su lista concatenata.
Coda o Queue
• La realizzazione della Coda su array è più complessa.
• Nella Pila si estraeva e si inseriva da un’unica parte: l’estremo destro dell’array
• Nella Coda decidiamo di: inserire a destra (in coda) e di estrarre a sinistra (in testa).
sp--
sp-- vett[0]
Coda o Queue
estrarre dalla testa
inserire in coda
• Costruiamo l’array:
int vett[6];
int qp;
//queue pointer: indica la prima posizione libera qp = 0; //Coda vuota;
• Per accedere alla testa:
restituire v[0]
Coda o Queue
• Per inserire un elemento in coda:
v[qp] = valore;
qp++;
L’array deve avere dimensione opportuna.
• Per togliere la testa ed avere la nuova testa nella prima posizione (qp=0) si devono ricopiare all’indietro gli elementi:
qp--;
for(int i = 0; i<qp; i++) v[i] = v[i+1];
Coda o Queue
• Questa realizzazione, efficiente per la Pila, è poco efficienteper la Coda.
• Nella Pila tutte le operazioni sono O(1).
• Nella Coda le operazioni sono O(1), tranne togli che è O(n): infatti per mantenere la struttura compatta, si devono sempre spostare tutti gli elementi.
• Per realizzare una Coda più efficiente usiamo due indici.
Coda o Queue
• Un indice vede il primo elemento, l’altro indice vede l’ultimo.
• L’ultimo rappresenta la prima posizione libera in cui inserire un nuovo elemento (inserimento in coda); il primo è la testa.
L’array è riempito nella parte centrale.
primo ultimo
Coda o Queue
• Abbiamo quindi:
int primo, ultimo;
primo = 0; //testa
ultimo = 0; //prima posizione libera
• Coda vuota: primo == ultimo
la prima posizione libera è la testa della coda
• accedere alla testa (se non è vuota):
restituire v[primo]
Coda o Queue
• togliere la testa (se non è vuota):
primo ++;
• inserire un elemento, in coda:
v[ultimo] = valore;
ultimo++;
• In tale modo tutte le operazioni sono O(1) la realizzazione con due indici è più efficiente.
• Nella realizzazione con array, sia per la Pila che per la Coda, c’è il problema della dimensione fissa dell’array.
Coda o Queue
• Rimane un problema.
• Supponiamo che l’array abbia 10 componenti (i=0, 1, 2, ..., 9), si inizia con coda vuota:
primo=0 e ultimo=0.
• Eseguiamo 10 operazioni di inserimento:
ultimo=10, che rappresenta Coda piena.
• Eseguiamo 10 operazioni di estrazione:
primo=ultimo, che rappresenta Coda vuota.
Coda o Queue
• Ora vogliamo inserire un nuovo dato: poiché ultimo = 10 non si può inserire, anche se la Coda è vuota: in tale modo lo spazio va
“perduto” .
• Si risolve il problema con la tecnica dell’array circolare: se c’è posto prima si può inserire il nuovo dato.
Coda o Queue
• Quando ultimo coincide con la lunghezza dell’array, si ritorna al valore iniziale, in tale modo si recupera lo spazio lasciato libero dall’eliminazione degli elementi, facendo “il giro”:
ultimo primo
Coda o Queue
• Aritmetica modulo m.
• Siano a ed m due numeri naturali, indichiamo con
a mod m il resto della divisione a/m Se m = 10 abbiamo:
per a < m a mod m = a
per a ≥ m ritroviamo come resti i valori compresi tra 0 e 9
Coda o Queue
• Se vogliamo realizzare il TDA Coda con una lista concatenata, utilizziamo due riferimenti:
primo vede la testa della Coda e ultimo vede l’ultimo elemento della Coda. Si inserisce con ultimo e si estrae con primo.
• Gli assiomi da realizzare sono: verifica se è vuota, estrai, inserisci, guarda la testa.
• Vedremo un modulo lista.c con tutte le funzioni per costruire i TDA Pila e Coda e tutte le operazioni di inserimento e cancellazione.
Lista
Lista
• La Lista è un TDA che generalizza il concetto di sequenza: gli elementi hanno un ordine posizionale. Nella Lista tutti gli elementi sono accessibili.
• La realizzazione con array è poco efficiente, la sua realizzazione “naturale” è con la lista concatenata.
• Il modulo lista.c contiene tutte le possibili operazioni per accedere ai vari elementi, inserire e rimuovere elementi in qualunque posizione.
Lista
• C’è un linguaggio di programmazione LISP (LISt Processor, 1958) basato sul concetto di lista.
• È un linguaggio funzionale: il programma è inteso come funzione.
• La lista viene definita attraverso i suoi assiomi (funzioni) e le funzioni possono essere composte per costruire altre funzionalità della lista.
Lista
• Le informazioni elementari che si vogliono rappresentare in una Lista si chiamano atomi.
• Dominio del TDA:
Dominio = {atomi, lista}= A ∪ LLLL LL
LL = {insieme di tutte le liste}
A = {insieme degli atomi}
costante = λ : lista vuota
funzioni = {isEmpty, head, rest, build}
(par. 11.2.2)
Lista
• Nel linguaggio LISP queste funzioni si chiamano:
isEmpty null
head car
rest cdr
build cons
• Vediamo il comportamento del TDA tramite i suoi assiomi, indipendentemente dalla sua realizzazione.
Lista
• Funzioni (assiomi) che definiscono la Lista:
• 1) isEmpty : L L L L →→→→ B B B B
true se llll = λ isEmpty(llll) =
false se llll≠ λ
• 2) head : L L L →L →→→ A
se llll≠ λ head(llll) = a head: restituisce la testa
llll a
Lista
• 1) rest : L L L →L →→ L → L L L
se llll≠ λ rest(llll) = llll' rest: toglie la testa
• 2) build : A ×××× L L L L →→→ L → L L L build(a, llll) = llll'
build: concatenazione atomo-lista costruisce la lista
llll
llll' a llll
llll'
Lista
• La Lista viene definita in generale tramite una definizione ricorsiva:
• una lista è:
• la lista vuota
• oppure, dato un atomo e una lista (che può essere λ) è la concatenazione dell’atomo alla lista.
• Con questa definizione ricorsiva vediamo come si può costruire la lista.
Lista
• llll = λ = () si parte da lista vuota
• a è un atomo; si può costruire la lista (a):
(a) = build(a, λ)
• aggiungiamo altri elementi: siano b e c atomi (b, a) = build(b,(a))
(c, b, a) = build(c, (b,a))
• Le funzioni si possono comporre e si possono costruire altre funzioni, con le quali si rappresenta l’accesso a tutti gli elementi della lista.
Lista
• Esempio.
• Sia L = (c, b, a)
head(L) = c rest(L) = (b, a)
componiamo le funzioni:
head(rest(build(c, (b, a)))) = b
head(build(c,(b, a))) = c
Lista
• L’insieme degli assiomi è completo: ogni altra funzione della Lista può essere espressa tramite gli assiomi. Si usano definizioni ricorsive.
• Esempio. Definiamo la lunghezza della Lista:
ln: L L L L →→→ →
0 se L = λ
len(L) =
1+ len(rest(L)) se L ≠ λ len((c, b, a)) = 1 + len((b, a)) = 1 + 1 + len((a)) =
= 1+ 1+ 1+ len(λ ) = 3
Lista
• Definiamo la fine della Lista (l’ultimo elemento)
end: L L L L →→→→ A solo se L ≠ λ head(L) se rest(L) = λ end(L) =
end(rest(L)) se rest(L) ≠ λ end((c, b, a)) = end((b, a)) = end((a)) =
= head((a)) = a
Lista
• Definiamo una funzione per aggiungere alla fine un elemento:
addToEnd: L L L L ××××A→→→→ L L L L
build(a, L) se L = λ addToEnd(L,a) =
build(head(L), addToEnd(rest(L), a)) se L ≠ λ
Lista
addToEnd(λ, a) = build(a, λ) = (a)
addToEnd((a), b) =
= build(a, addToEnd(λ , b)) =
= build(a, (b)) = (a, b)
addToEnd((a, b), c) =
= build(head(a,b), addToEnd(rest(a,b), c) =
= build(a, addToEnd((b), c) = build(a, (b,c)) =
= (a, b, c)
Lista
• Possiamo definire la funzione per togliere l’ultimo elemento (se L ≠ λ):
deleteFromEnd: L L L →L →→ L → L L L
rest(L) se rest(L) = λ deleteFromEnd(L) =
se rest(L) ≠ λ build(head(L), deleteFromEnd(rest(L))
• Si può anche definire la funzione per la concatenazione di due liste.
Dizionario
Dizionario
• Il dizionario è un TDA dove si vogliono eseguire ricerche dove l’informazione è individuata da una chiave che è unica.
• La parola del TDA deriva proprio dal dizionario (vocabolario) nel quale:
• le parole sono le chiavi di accesso e sono tutte distinte
• la definizione che segue la parola (informazione associata alla parola, attributo) caratterizza la parola.
Dizionario
• Un Dizionario è un contenitore di coppie:
Coppia = (chiave, attributo)
• la chiave è confrontabile: intero, stringa
• la chiave è unica: se si vuole inserire una chiave si deve verificare che non sia presente, se lo è si esegue una sostituzione.
• Le operazioni del TDA Dizionario sono:
• verifica se è vuoto
• inserimento
• ricerca
• cancellazione
Albero
Albero
• Un albero è un insieme di punti, detti nodi, a cui è associata una struttura d’ordine parziale (non tutti gli elementi sono confrontabili).
• Un albero binario è un TDA definito nel modo seguente:
• un insieme vuoto di nodi
• una radice con due sottoalberi sinistro e destro che sono alberi binari.
(par. 9.5)
Albero binario
• Il TDA albero binario si può realizzare con un array o con una lista concatenata.
• Nella realizzazione con lista concatenata utilizziamo due riferimenti per indicare i due sottoalberi:
struct tiponodo{
int chiave;
tiponodo *sinistro;
tiponodo *destro;
};
Albero binario
• Possiamo rappresentarlo graficamente nel modo seguente:
chiave sinistro destro
Albero binario
• Le foglie sono rappresentate con i due riferimenti uguali a NULL:
• Si considerano alberi binari completi, perfettamente bilanciati e bilanciati.
chiave
•
••
•
•
••
•
Albero binario
• Albero binario completo:
da ogni nodo partono sempre due rami e le foglie sono tutte allo stesso livello.
Albero binario
• Albero binario perfettamente bilanciato:
per ogni nodo il numero dei nodi del sottoalbero sinistro differisce al più di 1 dal numero dei nodi del sottoalbero destro.
Albero binario
• Albero binario bilanciato:
per ogni nodo le altezze dei sottoalberi sinistro e destro differiscono al più di 1.
Albero binario
• Un albero binario di profondità k perfettamente bilanciato è completo fino al livello k-1.
• Un albero binario completo BBBB
k ha n=2k+1-1 nodi e 2kfoglie (dimostrazione per induzione).
• Tutte le operazioni di ricerca di un nodo (inserimento e cancellazione) su un albero binario bilanciato (perfettamente bilanciato) hanno complessità O(log2 n).
Albero binario
• Albero binario di ricerca:
i valori dei nodi del sottoalbero sinistro sono minori della radice e quelli del sottoalbero destro sono maggiori della radice.
8 11 4
1 9 12
Albero binario
• Un albero binario di ricerca può essere totalmente sbilanciato; esistono delle tecniche di ribilanciamento che, con un numero finito
di assegnazioni sui puntatori, permettono di costruire alberi di ricerca bilanciati.
1
3
4 2
Albero binario
• Si può “visitare” un albero di ricerca esaminando i nodi in un ordine stabilito. Si hanno le seguenti tipologie di visita dell’albero:
• inordine A R B
• preordine R A B
• postordine A B R
dove R è la radice e A e B i sottoalberi sinistro e destro.
R
A B
Gestione hash di un array di interi
Gestione hash di un array di interi
• Vogliamo inserire dei numeri interi in un array e pensiamo ad una memorizzazione efficiente con lo scopo di ottimizzare successivamente la ricerca del numero.
• Esempio.
• Pensiamo di memorizzare in un array i numeri di matricola di un corso di n=180 studenti; alla matricola si possono poi far corrispondere ulteriori informazioni riguardanti lo studente.
Gestione hash di un array di interi
• Oppure potremmo pensare di individuare lo studente tramite la sua postazione al PC del laboratorio: in questo caso avremo 180 numeri diversi per i 180 studenti. In questo secondo caso consideriamo un array di dimensione 180 e memorizziamo al posto i-esimo lo i-esimo studente: l’indice dell’array coincide con l’informazione che vogliamo memorizzare:
indice = informazione
Gestione hash di un array di interi
• Se andiamo ad eseguire una ricerca il costo sarà sempre O(1); l’accesso diretto alla posizione i- esima ci fornisce l’informazione cercata:
postazione[i] = i
• Potremmo pensare di risolvere in modo analogo il problema di memorizzare il numero di matricola, supponiamo compreso tra 575000 e 580000. Se avessimo a disposizione un array di 580000 componenti nuovamente troveremmo la matricola cercata in un tempo O(1)
matricola[575231] = 575231
Gestione hash di un array di interi
• Possiamo vedere la matricola e la postazione come delle chiavi di accesso all’informazione vera, costituita dai dati dello studente. Se l’insieme delle possibili chiavi coincide con il numero di elementi che vogliamo rappresentare, come nel caso della postazione, allora la scelta è buona.
• Nel caso della matricola avremmo un notevole spreco di memoria: un array di 580000 componenti per memorizzare 180 dati.
Gestione hash di un array di interi
• L’idea pertanto è la seguente:
• lo spazio in più può dare dei vantaggi
• per non sprecarlo cerchiamo una funzione che trasformi la matricola (chiave) in un valore di indice possibile per un array di dimensione dim, con dim un po’ più grande di n=180.
• Vogliamo determinare una funzione h tale che, per ogni valore della chiave (matricola) si abbia:
h(chiave) = posizione con 0 ≤ posizione ≤ dim-1
Gestione hash di un array di interi
• Una funzione di trasformazione può essere il calcolo del resto della divisione con dim:
posizione = h(k) = k mod dim
• Si può dimostrare che, con questa scelta della funzione, è bene che sia dim ≥ n del 10-20% e che dim sia un numero primo. Infatti una buona scelta di h comporta che i resti siano, nella maggior parte dei casi, diversi tra loro.
• Se fosse dim=100, tutti i numeri del tipo 575100, 575200, . . ., 576100, 576200, . . ., avrebbero lo stesso resto.
Gestione hash di un array di interi
• Non sempre le chiavi troveranno resti diversi: si parla allora di “collisione” dato che due chiavi dovrebbero andare nello stesso posto. Come risolvere il problema?
• Lo spazio nell’array c’è, visto che dim ≥ n , pertanto si effettua una scansione cercando un
“posto libero”, provando con il successivo modulo dim:
se posizione = k mod dim è occupata, allora si cerca in
posizione = (posizione+1) mod dim
Gestione hash di un array di interi
• Come nella Coda, questa tecnica permette di
“fare il giro” dell’array.
• Esempio. Consideriamo i seguenti n=9 valori:
1, 3, 4, 15, 18, 20, 22, 35, 48
e proviamo ad inserirli con la tecnica del resto in un array di dim=11 elementi.
• Calcoliamo i resti:
1%11 = 1; 3%11 = 3; 4%11 = 4;
15%11 = 4 ma la posizione 4 è occupata
Gestione hash di un array di interi
• Facciamo:
(4+1)%11 = 5%11= 5 che è libera continuiamo:
18%11= 7; 20%11= 9; 22%11= 0;
35%11= 2; 48%11= 4 che è occupata:
(4+1)%11 = 5%11= 5 che è occupata (5+1)%11 = 6%11= 6 che è libera I numeri nell’array sono memorizzati in ordine diverso da quello di inserimento (rimescolati):
Gestione hash di un array di interi
0 1 2 3 4 5 6 7 8 9 10
• Quanto costa inserire con questa tecnica?
• L’inserimento di un numero che trova subito il suo posto è O(1): calcolo del resto, invece di +1; quando c’è una collisione si deve cercare il posto: se n=dim il caso peggiore è O(n), si fa tutto il giro; nel nostro caso abbiamo 12 confronti (per cercare il posto libero) per 9 elementi.
• Si può dimostrare che, se dim è “buona”, in media il costo è O(1).
22 1 35 3 4 15 48 18 20
Gestione hash di un array di interi
• Proviamo ora ad effettuare una ricerca di un valore nell’array. La tecnica per la ricerca sarà la stessa: calcolare il resto della divisione con dim:
valore%dim
fornisce l’indice in cui cercare il valore (chiave).
• Il costo della ricerca di un valore presente è lo stesso di quello dell’inserimento: in media O(1).
Per un valore non presente il costo è superiore:
può capitare di fare tutto il giro, O(n) nel caso peggiore.
Gestione hash di un array di interi
• Per costruire l’array dobbiamo dare un significato al posto “vuoto”. Possiamo inizializzare l’array con un valore non appartenente all’universo delle chiavi; ad esempio 0 per le matricole, -1 per le postazioni dei PC, ecc.
• Durante la costruzione dell’array il posto vuoto indica la posizione libera in cui poter inserire l’elemento.
• Durante la ricerca il posto vuoto indica
“elemento non presente”.
Gestione hash di un array di interi
• Nel caso della ricerca si effettua la stessa scansione facendo il giro dell’array. In caso di array pieno (n=dim) e di elemento non presente, si fa tutto il giro ritornando alla posizione iniziale senza trovarlo.
• Per gestire questa situazione, si salva il valore della chiave presente all’indice chiave%dim in una variabile temporanea, si copia in tale posizione l’elemento da cercare, si effettua la ricerca (che avrà esito positivo).
Gestione hash di un array di interi
• Se l’elemento viene trovato nella posizione iniziale (si è fatto tutto il giro) significa che non c’è, altrimenti lo si è trovato più avanti e ciò significa che c’era stata una collisione.
Infine si ripristina il valore salvato.
• Si può ottimizzare la ricerca del caso non trovato, inserendo le chiavi in ordine: se si trova un elemento più grande ciò significa che quello più piccolo non c’è.
Tavola Hash
Tavola Hash
• Un Dizionario con chiave intera viene chiamato Tavola.
• Nella costruzione dell’array di interi con la tecnica hash, avevamo risolto il problema delle collisioni con un sovradimensionamento della tavola; cerchiamo di risolverlo in altro modo:
mantenere le stesse prestazioni e non sprecare spazio.
• L’array offre con l’accesso diretto O(1), la lista concatenata offre un inserimento O(1).
Tavola Hash
• Costruiamo un array di liste concatenate: la scelta dell’indice nell’array si effettua con chiave trasformata (ridotta) e la collisione si risolve con un inserimento in testa alla lista.
• Abbiamo quindi un Tavola realizzata tramite due strutture di dati che prende il nome di Tavola Hash con bucket (bucket è la lista concatenata).
• Le prestazioni della Tavola dipendono dalla funzione hash e dalle chiavi.
Tavola Hash
• La funzione h potrebbe fornire sempre lo stesso valore di chiave ridotta: caso peggiore, O(n)
•
•
•
•
••••
coppia coppia coppia
Tavola Hash
• Caso favorevole: tutte le liste hanno la stessa lunghezza, n/dim, O(n/dim); se n~dim si ha circa O(1)
coppia
coppia
coppia . . .
Tavola Hash
• Se le chiavi sono uniformemente distribuite, la funzione hash con il resto della divisione con dimè una buona scelta: anche le chiavi ridotte sono uniformemente distribuite.
• Come fare se la chiave è una stringa?
• Dobbiamo associare ad una stringa un valore intero per poter poi calcolare il resto.
Tavola Hash
• Ricordiamo la notazione posizionale dei numeri:
257 = 2 ××××102+ 5 ×××× 101 + 7 ×××× 100
possiamo trasformare una stringa in un numero pensando alla base b = 256 (ASCII):
“ABC” = ‘A’ ×××× b2+ ‘B’ ×××× b1+ ‘C’ ×××× b0
• Sarebbe una buona idea, dato che in C++ un char è anche un intero piccolo, ma si avrebbe un numero troppo elevato e spesso overflow.
Tavola Hash
• Spesso per le stringhe viene usato il valore 31 (numero primo) come moltiplicatore, al posto di b:
“ABC” = ‘A’ ×××× 312+ ‘B’ ×××× 311+ ‘C’ ×××× 310
• Possiamo quindi calcolare il valore hash per ogni stringa.
Riepilogo TDA e strutture di dati
TDA
• Un Tipo di Dato Astratto è:
• un insieme di elementi chiamato dominio del tipo di dato
• caratterizzato da un nome
• possiede delle funzioni che operano sul dominio
• operatori, predicati, operatori di creazione
• possiede delle costanti che lo caratterizzano
TDA
• I seguenti TDA sono contenitori caratterizzati dalle loro diverse operazioni :
• Pila (Stack)
• Coda (Queue)
• Lista
• Dizionario e Tavola
• Albero
Strutture di dati
• Una struttura di dati è un modo di organizzarei dati in un contenitore di dati ed ha una sua propria modalità di accesso. Sono state viste le seguenti strutture:
• array
• lista concatenata.
Strutture di dati
Array Lista concatenata
accesso diretto sequenziale
successivo i+1 p->punt
dimensione massima sì no
spazio info info e punt
spostamento dati sì no
(inserire e cancellare)
Pila Stack (Last In First Out)
• Le operazioni coinvolgono solo il primo elemento della Pila.
• verifica di Pila vuota
• visione della testa
• inserimento in testa
• estrazione dalla testa
Coda o Queue (First In First Out)
• Le operazioni coinvolgono il primo elemento e l'ultimo elemento della Coda. Il TDA viene descritto nella seguente interfaccia:
• verifica di Coda vuota
• visione della testa
• inserimento in coda
• estrazione dalla testa
Lista
• Generalizza il concetto di sequenza: è un contenitore di informazioni che hanno un ordine posizionale.
• Si esegue una scansione lineare tramite una variabile che a partire dal primo elemento della lista si posiziona sull'elemento cercato (se esso è presente).
• In una lista si può accedere a qualunque elemento.
Dizionario o Dictionary
• E' costituito da coppie (chiave, attributo); la chiave è unica e deve permettere il confronto.
• Le operazioni che si possono fare sono:
• verifica se è vuoto
• ricerca di una chiave
• inserimento di una coppia
• rimozione della coppia
Tavola Hash
• Si esegue una trasformazione della chiave per ottimizzarne la memorizzazione:
posizione = h(chiave)
• h: resto della divisione intera chiave/dim
• dim: dimensione della tavola
• Si utilizzano assieme le due strutture dati costruendo un array di liste concatenate (bucket).
• Se le chiavi sono n e le liste hanno la stessa lunghezza, le prestazioni sono O(n/dim).
Il linguaggio C++
C++
• Il linguaggio C++ è un linguaggio di programmazione ad alto livello.
• Il linguaggio C++ è dotato di un compilatore che traduce il codice sorgente in un codice binario.
• Il compilatore, durante la traduzione in codice macchina, esegue una analisi lessicale, sintatticae semantica.
• Il codice binario viene elaborato dal linker che produce il codice eseguibile (aggancio dei vari moduli).
C++
• Un programma C++ è composto da una o più unità compilabili (moduli).
• Ciascuna unità contiene una o più funzioni e può contenere istruzioni chiamate "direttive"
per il preprocessore.
• L’istruzione include effettua l’inserimento del file indicato.
• Una sola unità contiene la funzione main.
Alfabeto
• L'alfabeto del linguaggio è costituito dai simboli del codice ASCII.
• I primi 128 caratteri vengono usati per scrivere le istruzioni e le unità lessicali del programma.
• Si distinguono le lettere minuscole dalle maiuscole.
• Lo spazio è un separatore.
• Le parole chiave (parole che hanno un particolare significato per il linguaggio) sono riservate (minuscole), ossia non si possono usare come nomi di identificatori.
Unità lessicali
• Le unità lessicali (token) con cui si costruiscono le frasi del linguaggio sono:
• identificatori
• parole chiave
• costanti
• separatori
• operatori
• I nomi degli identificatori sono costruiti con caratteri alfanumerici e devono iniziare con un carattere alfabetico .
Tipi di dato
• Abbiamo visto i seguenti tipi di dato predefiniti:
• intero
• reale
• carattere
• logico (non è nello standard)
• puntatori
• Si sono usate anche le struct del C per gestire record (collezione di elementi di tipo diverso).
Tipo Intero
• A seconda dell'occupazione in byte si hanno i seguenti tipi:
short (1, 2), int (2, 4), long (8).
• Degli n bit a disposizione, il primo è il bit del segno 0 positivi
1 negativi
• I rimanenti n-1 sono per il numero.
Tipo Intero
• Si possono rappresentare 2n -1 valori diversi.
• Costanti del tipo di dato:
- 2n -1 e 2n -1-1
che delimitano l'intervallo di rappresentazione.
• Dato x, per trovare la sua rappresentazione r(x)in base b (b=2) si divide per la base e si prendono i resti.
Tipo Intero
• La rappresentazione dell'opposto è definita in complementoa 2
r(x) + r(-x) = 2n
• Per trovare la rappresentazione dell'opposto, indicata con r(-x), si invertono tutti i bit di r(x) fatta eccezione degli 0 a destra e del primo 1 a destra (oppure si invertono tutti i bit e si aggiunge 1).
Tipo Reale
• A seconda dell'occupazione in byte si hanno i seguenti tipi: float (4), double (8) e long double (12).
• Dati n bit a disposizione il primo è il bit del segno
0 positivi 1 negativi
• Dei rimanenti n-1 bit si ha una ripartizione tra esponentee mantissa.
Mantissa
• I numeri reali sono rappresentati in modulo e segno, riferiti alla base 2, con mantissa normalizzata e bit nascosto.
• Dato x per costruire la rappresentazione r(x) si deve trasformare in binario il numero reale:
parte intera: si divide per la base e si prendono i resti
parte frazionaria: si moltiplica per la base e si prendono e parti intere
• Si deve poi portare il numero binario in forma normalizzata 1.c1c2c3.... ×××× 2e
Esponente
• L'esponente e viene rappresentato con l'eccesso (in traslazione) vale a dire che e deve essere aumentato di 127 per i float (eccesso). Il nuovo esponente (intero) viene trasformato in binario.
• Costanti del tipo di dato
minimo reale ≠ 0 float ~ 10-38 massimo reale float ~ 1038
Funzione
• Una funzione può avere zero, uno o più argomenti ed ha un esplicito valore scalare di ritorno.
• Ogni funzione è caratterizzata dal tipo del valore restituito.
• Se una funzione non restituisce esplicitamente un valore, allora il suo tipo di ritorno è void.
Variabile locale
• Si chiama blocco un gruppo di istruzioni all'interno di una coppia di parentesi graffe.
• Ogni funzione contiene uno o più blocchi.
• Una variabile locale è nota (visibile) solo nel blocco in cui è stata definita.
• All’interno del blocco deve essere definita una ed una sola volta.
Variabile di scambio o parametro
• Una variabile di scambio è una variabile che permette la comunicazione dell’informazione tra funzioni.
• Parametro formale: parametro che appare nella intestazione della funzione.
• Parametro attuale: parametro (argomento) che appare nell'istruzione di chiamata della funzione.
• La corrispondenza tra i parametri è posizionale.
Passaggio dei parametri
• Il passaggio dei parametri nella chiamata di una funzione (sottoprogramma) può essere:
• per valore:
• nel sottoprogramma chiamato viene costruito un nuovo spazio per la variabile e in esso viene copiato il valore (scalare)
• per indirizzo:
• al programma viene passato l'indirizzo di memoria della variabile (per gli array viene passato l’indirizzo della prima componente).
Variabile locale
Una variabile locale:
• appartiene a un blocco o ad una funzione
• è visibile all'interno del blocco o della funzione
• deve essere inizializzata esplicitamente
• viene creata, "nasce", quando viene eseguitol'enunciato in cui è definita
• viene eliminata, "muore", quando l'esecuzione del programma esce dal blocco nel quale è stata definita
Variabile parametro
Una variabile parametro (formale):
• appartiene a una funzione
• è visibile all'interno della funzione
• viene inizializzata all'atto della invocazione della funzione (con il valore fornito dall'invocazione)
• viene creata, "nasce", quando viene invocatala funzione
• viene eliminata, "muore", quando l'esecuzione della funzione termina
Allocazione in memoria
• La definizione delle variabili comporta una allocazione di spazio durante la compilazione del programma. Lo spazio di memoria utilizzato si chiama Stack.
• Durante l'esecuzione del programma si può allocare dello spazio con la funzione new. Lo spazio di memoria utilizzato si chiama Heap.
Stack e Heap
• Rappresentano parti diverse della memoria: Stack (tipi base) e Heap (elementi creati con new).
• Schema della disposizione degli indirizzi di memoria:
lunghezza cresce verso → ← cresce verso fissa la memoria alta la memoria bassa
Codice di
programma RuntimeStack Memoria
libera Heap
indirizzi di memoria crescenti
Algoritmi
Algoritmi
• Un algoritmo (deterministico) è un procedimento di soluzione costituito da un insieme di operazioni eseguibili tale che: esiste una prima operazione, dopo ogni operazione è individuata la successiva, esiste un'ultima operazione.
• La risoluzione avviene in due passi:
• analisi, definizione del problema e progettazione
• codifica, trasformazione in un linguaggio di programmazione
Strutture di controllo
• Con le seguenti strutture di controllo si può scrivere qualsiasi algoritmo:
• sequenza
• alternativa
• ciclo
• Queste strutture sono caratterizzate dall'avere un unico punto di ingresso e un unico punto di uscita.
Iterazione e Ricorsione
• La scomposizione in sottoproblemi può essere:
• iterativa:
• i sottoproblemi sono simili tra loro
• ricorsiva:
• almeno uno dei sottoproblemi è simile a quello iniziale, ma di dimensione inferiore
• In entrambe le scomposizioni si pone il problema della terminazione.
Divide et impera
• E' una strategia generale per impostare algoritmi:
• suddividere l'insieme dei dati in un numero finito di sottoinsiemi sui quali si può operare ricorsivamente.
• Se la suddivisione in sottoinsiemi è bilanciata (sottoinsiemi di uguale dimensione) si ottengono algoritmi efficienti.
Complessità
• L'efficienza di un algoritmo si valuta in base all'utilizzo che esso fa delle risorse di calcolo:
memoria (spazio), CPU (tempo).
• Il tempo che un algoritmo impiega per risolvere un problema è una funzione crescente della dimensione dei dati del problema. Se la dimensione varia, può essere stimato in maniera indipendente dal linguaggio, dal calcolatore e dalla scelta di dati, considerando il numero di operazioni eseguitedall'algoritmo.
Complessità computazionale
• Indicata con n (numero naturale) la dimensione dei dati di ingresso, la funzione F(n) che calcola il numero di operazioni viene chiamata complessità computazionale e utilizzata come stima della complessità di tempo.
• Si fanno delle semplificazioni individuando quali operazioni dipendono da n.
Andamento asintotico della complessità
• Se F(n) è crescente con n e se si ha che:
F(n) → +∞ per n → +∞
• date le semplificazioni per la valutazione di F(n), si stima il comportamento della funzione per n→+∞
utilizzando le seguenti notazioni:
• O(o-grande) limitazione superiore
• Ω(omega) limitazione inferiore
• Θ(theta) ugualeandamento
Calcolo della complessità
• Nel calcolo della complessità si valuta il comportamento dell'algoritmo su particolari scelte di datie si distinguono:
• un caso peggiore in cui l'algoritmo effettua il massimonumero di operazioni,
• un caso favorevole in cui l'algoritmo effettua il minimonumero di operazioni,
• un caso medio in cui l'algoritmo effettua un numero medio di operazioni.
Calcolo della complessità
• Quando si scrive un algoritmo si deve sempre dare una stima del caso peggiore e di quello favorevole.
• Se la dimensione n dei dati non varia, la funzione di complessità è costante.
• Se n si mantiene limitato le considerazioni asintotiche non valgono.
Classi di complessità
• Le funzioni di complessità sono distinte in classi che rappresentano i diversi ordini di infinito
O(1) costanti
O(log (log n))
O(log n) logarimto
O(n) lineari
O(n*log n)
O(nk) polinomi k = 2, 3, ...
O(n!), O(nn), O(an) esponenziali (a ≠ 0,1)
• Gli algoritmi con complessità esponenziale sono impraticabili
