Riassunto degli argomenti di teoria

O

termini di .       



Θ

  

k, f n , k f n = f n

1. Fattore costante:

    

     

     



Θ Θ Θ



f n = g n , g n = h n f n = h n

2. Transitività:

  

   

      





Θ Θ Θ

f n + g n = max f n , g n

3. Somma:   

   

     



Θ Θ Θ

 

f n g n = f n g n

4. Prodotto:

 Complessità di funzioni ricorsive:

1. Divisione della struttura dati in due parti, invocazione ricorsiva su una sola delle due

parti e tempo di combinazione e divisione costante:

c se n = 1

 1



     

 

T n = T n = c + c log n

n

   1 2 2

T + c se n > 1

 

 2

2

 



2. Divisione della struttura dati in due parti, invocazione ricorsiva su entrambe le parti e

tempo di combinazione e divisione costante:

c se n = 1

 1



     

  

T n = T n = n c + n 1 c

n

   1 2



2 T + c se n > 1

 

 2

2

 



3. Divisione della struttura dati in due parti, invocazione ricorsiva una sola delle due parti e

tempo di combinazione e divisione lineare:

c se n = 1

 1



   

 

T n = T n = c + 2n c

n

   1 2



T + n c se n > 1

 

 2

2

 



4. Divisione della struttura dati in due parti, invocazione ricorsiva su entrambe le parti e

tempo di combinazione e divisione lineare:

c se n = 1

 1



     

   

T n = T n = n c + n log n c

n

   1 2 2

 

2 T + n c se n > 1

 

 2

2

 



5. Divisione della struttura dati in due parti, una di dimensione 1 ed una di dimensione n-1,

effettuata con un'unica ricorsione e tempo di combinazione e divisione costanti:

c se n = 1



     

1   

T n = T n = c + n 1 c

   1 2



T n 1 + c se n > 1

 2

Algoritmi di ricerca:  

Θ

T = 1

 b

 n n

  

       

 Lineare: Θ Θ Θ Θ Θ



T = 1 + 1 = + 1 = n

 

 a 2 2

 

  

 Θ

T = n

 w  

Θ

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