Riassunto degli argomenti di teoria

 

Θ

T = 1

 b

         



Θ Θ Θ

 

Dicotomica: , la ricerca dicotomica necessita di un

T = log n 1 + 1 = log n

 a 2 2

   



Θ

T = log n

 w 2

array già ordinato. n

n = 1

n = 1 numero di elementi da esaminare, numero totale di elementi. , quindi

n =

i i i

2

i

all'aumentare di diminuisce n cioè, diminuisce il numero di elementi da

i  

i

i 

 

esaminare, . Se 2 = n i = log n , quindi, il numero di iterazioni

n = 0 2 > n 2

i  

i log n

compiute vale .

2

Algoritmi di ordinamento:

 Tipologie:

1. Ordinamento interno: se la struttura dati è interamente contenuta nella memoria centrale

2. Ordinamento esterno: se le struttura dati è contenuta, almeno in parte, in un file

3. Ordinamento sul posto: sfrutta la struttura dati iniziale

4. Ordinamento non sul posto: sfrutta strutture dati di appoggio

5. Ordinamento stabile: si aggiunge il vincolo che nella struttura dati finale gli elementi

equivalenti mantengano lo stesso ordine relativo

6. Ordinamento per confronti: confronta gli elementi a due a due per ordinarli

 Algoritmi principali

1. Selection sort: scorre l'array e scambia ad ogni passaggio il valore più piccolo trovato

con l'elemento che si trova alla prima posizione utile a partire dalla testa dell'array.

L'algoritmo è composto da due cicli for, uno per la posizione utile e uno per scandire la restante

parte non ordinata.

 

2

Θ

T = T = n

b w

2. Insertion sort: scorre l'array con due cicli for, uno per tener conto della parte già ordinata

e uno per gestire quella da ordinare.

Quest'algoritmo, in particolare, realizza una scansione della parte non ordinata confrontando gli

elementi tra di loro; non appena viene rilevato il più piccolo della parte non ordinata, si fanno

slittare in avanti tutti quelli non ordinati e si inserisce in testa. Successivamente si ciclo più esterno.

 

Θ → ad ogni scansione, l'elemento

T = n da inserire è più grande di quelli già ordinati; ovvero

b

l'array è ordinato

 

2

Θ

T = T = n

w a

3. Bubble sort: l'algoritmo scorre tutto l'array varie volte fino a quando non è ordinato e ad

ogni passaggio scambia la posizione dell'elemento più piccolo facendolo man mano

risalire a bolle verso la testa dell'array. Non appena si arrestano gli scambi l'algoritmo

finisce.

 

Θ

T = n

b  

2

Θ

T = T = n

w a

4. Merge sort: la funzione merge_sort spezza l'array tramite procedura ricorsiva e lo

suddivide fino a quando si arriva ad elementi singoli. Dopodiché viene richiamata la

funzione merge che fonde man mano le componenti suddivise in maniera tale che si

ottengano sottoarray ordinati che a loro volta vengono fusi tramite merge e rimandati

alla procedura chiamante. L'algoritmo si arresta quando si rientra nella prima procedura

chiamante.  

Θ

La funzione merge ha complessità: T = T = n

w b n

 

      



Θ Θ

 

T n = 2 T + n = n log n

La funzione merge_sort ha complessità:   2

2

 

5. Quick sort: è un ordinamento sul posto. Si partiziona l'array rispetto ad un elemento

detto pivot andando a disporre alla sinistra del pivot tutti gli elementi più piccoli e a

destra tutti quelli grandi. L'algoritmo si svolge tramite la funzione partition che scambia

i posti (viene attivata solo se ha almeno due elementi da confrontare) poi tramite

chiamata ricorsiva della funzione quick_sort l'array viene spettetato in unità più piccole

sulla quali applicare partition, cosicché proprio la funzione partition riposizionare il tutto

in maniera corretta.          

Θ Θ Θ

 

T n = n 1 1 + 1 = n

La funzione partition ha complessità:

La funzione quick_sort ha complessità:

 Se il pivot è preso al centro

   

Θ

T 1 = 1

 b

     



Θ

 

dell'array: T n = n log n

n

  

    w 2

Θ 

T n = n + 2 T  

 w w 2

 

    

Θ

T 1 = 1

 b



 Se il pivot è preso all'inizio o alla fine: n

          



Θ Θ



T n = n + T n 1 + T 1 = k = 1

 w w w

 k = 0

   

Θ

T 1 = 1

 w

  



n n + 1

    

2

Θ Θ

1 = = n

 

 2

 



Struttura dati:

 Statica: bisogna specificare il numero di elementi della struttura in fase di creazione

 Dinamica: è possibile modificare il numero di elementi durante l'esecuzione

1. Array dinamici: la struct modello array dinamico utilizza tre informazioni: il puntatore

all'area di memoria che contiene gli elementi dell'array, il numero di elementi effettivamente

utilizzati (lunghezza), la capacità massima.

struct mod_array_dinamico{

Tinfo *item;

int lunghezza;

int capacita;

}; funzioni: array_create(int lunghezza_iniziale)

array_destroy(Tarray *a)

array_resize(Tarray *a, int nuova_dimensione)

L'operazione di ridimensionamento di un array è un'operazione costosa. Si suddivide in:

1. allocazione di nuova memoria

2. copia dei vecchi elementi nella nuova area

3. deallocazione della vecchia area

Bisogna cercare di ridurre le operazioni necessarie procedendo come segue:

1. se si espande, bisogna allocare una capacità maggiore di quella richiesta

2. se si contrae, si dealloca solo quando la differenza tra lunghezza effettiva e capacità

supera una certa soglia

Esistono due tipologie di espansione:

1. Espansione lineare: quando la lunghezza richiesta è n e la capacità attuale è c:

Δ

 n > c

se si rialloca una capacità n + GROW

Δ Δ

 

se n < c si rialloca una nuova capacità n +

SHRINK GROW

 altrimenti l'array non viene riallocato

Δ Δ



NOTA: SHRINK GROW

2. Espansione geomatrica: prevede che la capacità supplementare sia proporzionale alla

lunghezza richiesta:

 

n > c

se si rialloca una capacità n P

GROW

c

 

n <

se si rialloca una capacità n P

GROW

P

SHRINK

 altrimenti l'array non viene riallocato



NOTA: P P

SHRINK GROW  

Θ n

Sia l'espansione lineare che quella geometrica hanno complessità spaziale .

n

In merito alla complessità temporale l'espansione lineare per riallocazioni comporta

   

2 Θ

Θ n

complessità n , invece quella geometrica .

2. Pila: è una collezione di elementi che restringe le modalità di accesso ad una logica LIFO; è

possibile accedere solo all'elemento inserito per ultimo.

Vantaggi: non è necessario indicare l'elemento al quale si vuole accedere, né la sua posizione inoltre

si evita che per errore il programma acceda ai dati in ordine errato.

Operazioni principali:

 creazione

 distruzione

 push o inserimento

 pop o estrazione

 top o consultazione cima

 controllo pila vuota

 controllo pila piena

3. Coda: è una collezione di elementi che restringe le modalità di accesso ad una logica FIFO;

è possibile accedere solo all'elemento inserito per primo

Vantaggi: il fatto che i dati sono elaborati in ordine di arrivo rende più predicibile il

comportamento del sistema, inoltre essi vengono elaborati dopo un tempo finito e non sono

scavalcati da altri dati pervenuti successivamente.

Operazioni principali:

 creazione

 distruzione

 add o accodamento

 remove o prelievo

 front o consultazione primo elemento

 controllo coda vuota

 controllo coda piena

4. Lista: è una struttura dati per rappresentare insiemi di dati; adotta uno schema di

rappresentazione in cui sono contenuti contemporaneamente l'informazione utile (info) e

l'informazione strutturale che serve a realizzare l'intera collezione.

1. Concatenata: collezione realizzata in strutture dette nodi; ogni nodo contiene l'info e il

link al nodo successivo; il primo nodo è detto testa, l'ultimo è detto coda

2. Doppia: ogni nodo contiene sia il collegamento al nodo successivo che a quello

precedente

3. Circolare: ogni nodo ha il collegamento al nodo successivo e l'ultimo nodo ha il

collegamento alla testa della lista

4. Circolare doppia: ogni nodo ha il collegamento al nodo successivo e al nodo precedente,

l'ultimo nodo ha il collegamento alla testa della lista e il primo nodo ha il collegamento

alla coda

5. Ordinamento di una lista:

 Fisico: relazione esistente tra la posizione dei nodi nella lista

 Logico: relazione esistente tra le info dei nodi

Operazioni principali iterative:

 

Θ

 crea_nodo: T = T = 1

w b  

Θ

 distruggi_nodo: T = T = 1

w b

 

Θ

 crea_lista: T = T = 1

w b    

Θ Θ

 distruggi_lista: T = n ,

T = 1

w b

   

Θ Θ

 search: T = n ,

T = 1

w b

   

Θ Θ

 inserimento: T = n ,

T = 1

w b

   

Θ Θ

 eliminazione: T = n ,

T = 1

w b

 

Θ

 stampa: T = T = n

w b  

Θ

 lista_vuota: T = T = 1

w b

Operazioni principali ricorsive:

 

Θ 1 se n = 1



   

 stampa: Θ



T n = T = T = T = n

 w b a

   

Θ 

1 + T n 1 se n > 1

  

Θ 1 se n = 1



     

 ricerca: Θ Θ



T n = T = T = n , T = 1

 w a b

   

Θ 

1 + T n 1 se n > 1

  

Θ 1 se n = 1



     

 inserimento: Θ Θ



T n = T = T = n , T = 1

 w a b

   

Θ 

1 + T n 1 se n > 1

  

Θ 1 se n = 1



     

 cancellazione: Θ Θ



T n = T = T = n , T = 1

 w a b

   

Θ 

1 + T n 1 se n > 1



Tabelle hash: