Ci sono dei dettagli tecnici che vediamo brevemente .
Nel primo enunciato abbiamo un , quindi questo vuol dire che
deve crescere più lentamente di e inoltre essere asintoticamente più piccola di
almeno un fattore (con l'esponente > 0)
ci deve essere un po' di margine per cui non solo vado più lentamente all' infinito , ma in più
ho anche un margine
Nel terzo caso stessa cosa ma dall' alto (è lo stesso discorso simmetrico)
Inoltre deve soddisfare la "condizione di regolarità" , cioè che non deve fare salti (non
deve essere una funzione "strana" )
Teorema dell' ipotesi di regolarità
Se ho una funzione che è asintoticamente non decrescente e riesco a
dimostrare che il tempo di esecuzione dell' algoritmo è per tutti gli della forma
, con e , allora posso estendere questa conclusione a tutti i valori
di
a condizione che $f(n)$ sia anche regolare, cioè che raddoppiare l’input non
cambi l’ordine di grandezza della funzione ($f(2n) = \Theta(f(n))$).
Lo useremo qualche volta per calcolare la complessità di un algoritmo .
Ordinamento di vettori
Il primo ordinamento che vediamo è detto "ordinamento per fusione" .
MergeSort
Questo è un algoritmo semplice ma estremamente furbo, è uno dei migliori mai inventati (non
per tutti ) ed è il più efficiente che abbiamo visto fino ad adesso.
Ha un unico piccolo difetto , ovvero che non è facilmente utilizzabile con grandi dimensioni di
dati .
Tip
"Questo è un buon algoritmo di ordinamento da citare al colloquio di lavoro (con la tappulli
SRL) "
Tip
L'ha inventato Von Neumann (ArchitetturaDeiCalcolatori > Componenti fondamentali)
L'idea è quella di "dividi e conquista " : devo ordinare un vettore di elementi , allora divido in
due il vettore ordinando le due metà ricorsivamente,questo perchè vedremo che combinare due
vettori ordinati è più facile .
Avendo due liste ordinate o vettori , produrre una fusione delle due strutture è semplice :
inizio dall'array disordinato e lo spacco a metà ricorsivamente fino ad ottenere ogni elemento
"da solo" , a quel punto ogni array ha solo un elemento e quindi è ordinato per definizione .
A questo punto dobbiamo ritornare indietro (poichè è un algoritmo ricorsivo) e quindi riuniamo le
parti precedentemente spaccate , le confrontiamo e le ordiniamo in base all'ordine che
vogliamo .
Andando avanti così riuniamo le parti spaccate ordinandole .
Alla fine avremo due vettori ordinati : confrontiamo il primo elemento col primo elemento e li
inseriamo in base all'ordine che vogliamo nell' array finale ordinato , iterando così per ogni
indice dei due vettori fino ad ottenere un array ordinato .
Alla fine avrò operazioni da fare su ogni lista , andando avanti si dimezzerà sempre di più
questo numero .
"spacco , spacco , spacco" e poi ritorno in cima riordinando i pezzi spaccati.
Vediamo un esempio :
è à
Quindi diventa :
MERGESORT(A : Item[ ]){ //prendo il vettore A disordinato
n ← [Link] //salvo la dimensione di A
if n > 1 then{//se il vettore non ha un solo elemento procedo
mB ← n/2; //si calcola la dimensione della prima metà del vettore prendendo
la parte inferiore di n/2 ( non è detto che n sia pari )
mC ← (n − n/2) //e anche del secondo vettore
B ← new Item[mB ]; C ← new Item[mC ]; //alloco due nuovi vettori
//e copio le due parti qua dentro
COPY(A, B, 0, n/2 − 1)
COPY(A, C, n/2, n − 1)
//ordino la prima meta e poi la seconda meta
MERGESORT(B)
MERGESORT(C)
//e alla fine faccio un ultimo ordinamento sui due vettori che sono risaliti
ordinati
MERGE(B, C, A)
}
}
COPY(A, B : Item[ ], lo, hi : Natural)
j ← 0
for i ← lo to hi do
B[j] ← A[i]
j ← j + 1
MERGE(B, C, A : Item[ ])
mB ← [Link]; mC ← [Link] //memorizzo le dimensioni dei due vettori
i ← 0; j ← 0; k ← 0; //inizializzo gli indici dei vettori
while i < mB and j < mC do //fin quando entrambi i vettori hanno ancora
elementi da confrontare ...
if B[i] ≤ C[j] then//confronta i primi elementi non ancora usati dei due
vettori
A[k] ← B[i]; i ← i + 1 //e se l'elemento di B è minore ci va lui prima in A
else
A[k] ← C[j]; j ← j + 1//se no ci va prima l'elemento di C
k ← k + 1 //avanziamo nel vettore finale A l'indice
//usciti da ciclo principale :
if i = mB then//se il vettore B è stato analizzato tutto ...
while j < mC do//copio tutti gli elementi di C dentro A
A[k] ← C[j]; j ← j + 1
k ← k + 1
else//e se no è finito il vettore C e faccio la stessa cosa con B
while i < mB do
A[k] ← B[i]; i ← i + 1
k ← k + 1
Analisi di MergeSort
Assumiamo come :
dimensione dell' input
operazione di base il confronto tra e dell' if in
Però non sto considerando le code finali . Questo problema per il momento notiamolo
ma non aggiustiamolo .
dipendenza dall' input il caso pessimo in cui gli elementi di e sono ordinati in modo
alterno , cioè che dovremo confrontare elemento per elemento fino alla fine degli indici di
tutti e due i vettori , ad esempio
per quanto sia pessimo , il costo sarà
Il costo complessivo dell’algoritmo è per definizione :
Tip
Stiamo trascurando un' ipotesi .
Io ho detto che prendo i confronti come operazione di base , però i confronti sono solo
dentro una parte del codice , non sono nella copy e inoltre non sto contando le
code finali come già detto.
Stiamo trascurando tante cose , ma andiamo avanti .
Caso pessimo
Il costo di di elementi è :
E applicando il Master Theorem riconosco dalla formula che :
in ogni nodo pago che asintoticamente lo valuto come
ho "foglie dell' albero di ricorsione" e quindi
(la proprietà dei logaritmi è questa : )
quindi riconosco che "le foglie" e "l'altezza dell' albero" hanno la stessa crescita e allora applico
il secondo enunciato (ProgrammaAC > Master Theorem > Secondo enunciato) .
Ottengo il numero delle foglie per l'altezza dell' albero :
Tip
Il costo ha e non perchè stiamo analizzando il caso pessimo, quindi diciamo che il
costo aumenta "fino a quel punto al massimo" e non "esattamente fino a quel punto" .
Possiamo concludere che la complessità di ha complessità .
Tip
L'ultimo algoritmo più efficiente che avevamo visto costava , quindi per ora questo è il
migliore algoritmo di confronto e dimostreremo che è anche "ottimo"
Prendere i confronti come operazione di base abbiamo visto che ha dei problemi , nel senso
che trascuriamo molte cose .
Quindi ci chiediamo cosa cambia se l'operazione di base è il numero di accessi in memoria .
sarebbe un operazione che si trova dappertutto nell'algoritmo , quindi assumiamo questa come
operazione di base.
Analisi di MergeSort 2.0
La modifica in questa analisi è prendere come operazione di base gli accessi in memoria .
Mentre prima i confronti dipendevano dall'input e potevo farne più o meno a seconda di che
struttura avevano i vettori, adesso invece con gli accessi in memoria come operazione di base
non possiamo non tenere conto di tutti i costi che prima "scappavano all'occhio" : in questo
caso la funzione ha un costo anche lei ; anche nella ora dobbiamo considerare
quando viene ricostruito il vettore finale di elementi .
Il costo quindi è questo :
E non abbiamo più caso pessimo e caso ottimo , dipendendo dagli accessi in memoria abbiamo
sempre accessi da fare (cioè che non c'è un caso in cui accedi alla memoria meno volte di un
altra , in ogni caso dovrai lavorare con tutti gli elementi a prescindere) e quindi otteniamo
questo costo , che non cambia molto da quello precedente :
che diventa attraverso il secondo enunciato del master theorem :
Tip
Possiamo concludere che se consideriamo gli accessi in memoria e non i confronti ,
abbiamo esattamente un costo pari ad .
Che comunque è sempre meglio di , che faceva accessi in memoria
(ProgrammaAC > Analisi di SelectionSort).
Memoria aggiuntiva utilizzata da MergeSort
Ora ci poniamo un altro problema , in non andavamo ad allocare memoria
aggiuntiva mentre invece si :
questa cosa per dimensioni grandi di vettori non è positiva , immaginando ad esempio 1 milione
di elementi su cui lavorare diventa problematico . Inoltre ricordiamoci che vogliamo andare ad
allocare spazio sulla memoria RAM e potrei non avere spazio disponibile .
Analisi grafica
Una domanda da esame su questo argomento può essere :
Dato un grafo non orientato , dare un algoritmo per stabilire se esso è connesso o meno .
La soluzione è usare o con un accorgimento in più : la lancio una sola volta
partendo da un nodo qualsiasi e se alla fine della ricerca non ho tutti i nodi del grafo
allora significa che c'è qualche nodo disconnesso dal resto .
Quindi all' esame copio il codice o (che devo conoscere riga per riga) però
senza il secondo for nella funzione principale e appena ritorna la chiamata alla funzione
controllo se il vettore segna tutti neri o meno .
Ora ritorniamo al discorso del nostro grafo diretto , non per forza fortemente connesso :
Se il grafo è diretto (o orientato, sto dicendo la stessa cosa) allora la connessione topologica
non implica che da un nodo si possano raggiungere tutti gli altri nodi , perchè alcuni archi vanno
solo in una direzione .
Possiamo concludere l'introduzione alle dicendo che :
Nei grafi non orientati il concetto di componente fortemente connessa è inutile , tutte le
componenti lo sono a priori . Quindi parliamo di "componenti connesse" e basta .
Nei grafi orientati si parla invece di "componenti fortemente connesse" perchè non è ovvio
che ci siano . Una si crea quando un nodo può raggiungere un altro nodo
seguendo la direzione unidirezionale dell'arco e poi attraverso uno o più nodi intermedi si
può ritornare a
Vediamo un esempio qui sotto con un grafo non orientato e connesso
ora usiamo un grafo non orientato perchè è più semplice da capire, nei prossimi passaggi
considereremo una versione orientata e connessa
Qua sopra vediamo 4 componenti "fortemente connesse"
( ha usato il termine "fortemente" anche se abbiamo appena detto che per grafi non orientati
non ha senso dirlo perchè stiamo ragionando già in ottica di grafi orientati , in vista dei passaggi
che vedremo dopo )
Se io sono in ma ho la sfortuna di infilarmi in , non posso tornare indietro e questo
potrebbe portare problemi .
Tip
Tra poco useremo tutti questi concetti per chiederci quanti e quali sono le componenti
fortemente connesse all' interno di un grafo orientato .
Grafo delle componenti fortemente connesse
Facciamo adesso uno step in più :
se noi rappresentiamo ogni componente fortemente connessa dell' immagine precedente con
un nodo unico e poi andiamo a mettere una freccia diretta fra una componente fortemente
connessa e un' altra creiamo un'astrazione del grafo , chiamata " grafo delle componenti
fortemente connesse" .
Tip
Il grafo delle componenti fortemente connesse è aciclico, perchè se ci fosse per esempio
un ciclo tra altri nodi , allora potrei creare delle componenti fortemente connesse diverse
da quelle attuali e il grafo di astrazione cambierebbe .
2. l'albero è perfettamente bilanciato
il caso pessimo è quando :
3. devo arrivare fino alle foglie
4. la chiave non è presente , quindi sono dovuto arrivare alla foglia finale che equivale all'
altezza dell' albero
Però a noi non ci piace , non me ne frega di studiare in funzione dell' altezza , vorrei
studiare in funzione degli elementi .
Tip
Studiamo la complessità in termini del numero dei nodi , quindi ora ci basiamo sui teoremi
descritti precedentemente in ProgrammaAC > Proprietà degli alberi binari .
Caso ottimo
In un albero completo di altezza , il numero totale di nodi , come sappiamo , è:
Andiamo a risolvere per :
Quindi posso concludere che , poichè l’albero completo “bilancia” la ricerca dimezzando lo
spazio ad ogni passo :
Tip
Un albero binario completo equivale ad un array ordinato
Danger
Una domanda d'esame è "Passare da un array ordinato ad un "
Caso pessimo
Se l’albero è del tutto sbilanciato equivale ad una lista e l'altezza posso esprimerla come :
Quindi:
In questo caso l’algoritmo degenera a una ricerca sequenziale.
Tip
Avevamo visto una situazione uguale nell' algoritmo , dove la funzione
veniva eseguita volte
(addirittura se l'input era ordinato ci dava il caso pessimo )
(il fatto che arrivavamo a dire che il costo fosse quadratico non c'entra , stiamo parlando di
una due cose diverse . Un conto è parlare di quanto costa ogni , un altro conto è
parlare di quanto costa complessivamente l'algoritmo che esegue )
ProgrammaAC > Analisi QuickSort > Caso pessimo
Osservazione personale
facendo l'analisi di abbiamo indirettamente trovato anche le formule
istantanee per capire subito l'altezza di un albero binario bilanciato o sbilanciato, quindi :
perchè se applichiamo la formula del master theorem usiamo
ProgrammaAC > Ricorrenze "Dividi e conquista" e Metodo dell' esperto
(Dove sono il numero dei nodi)
Alla fine quindi non è così tanto importante capire cosa succede nel caso ottimo o nel caso
pessimo , ma più che altro è meglio concentrarsi sul caso medio .
Caso medio
Anche per i vale una considerazione uguale a quella fatta con :
gli alberi binari di ricerca sono importanti perchè nonostante abbiano un caso pessimo lineare ,
quindi non migliore della ricerca in array disordinati , si può dimostrare che a meno che l'albero
non sia completamente sbilanciato, comunque la complessità della ricerca rimane logaritmica
Tip
Non abbiamo dimostrato questa cosa
ProgrammaAC > QuickSort > Caso medio .
Ora vediamo il ragionamento :
Tip
Non so quanto importante sia sapere bene questi ragionamenti
Supponiamo di avere un albero in cui, per ogni nodo, una frazione pari a dei discendenti
si trova nel sottoalbero di destra (o sinistra).
Allora, per l'altezza e il numero di nodi , vale l'equazione:
Da questo, si ottiene il limite superiore dell’altezza:
Come visto per il caso medio di QuickSort (ProgrammaAC > Analisi QuickSort > Caso medio) ,
risulta che: