Riassunto degli argomenti di teoria
Anteprima
ESTRATTO DOCUMENTO
Θ
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:
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher luckylucianooo di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico delle Marche - Univpm o del prof Ribighini Giuseppa.
Acquista con carta o conto PayPal
Scarica il file tutte le volte che vuoi
Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato