# Algoritmi/L'analisi di complessità degli algoritmi

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario
L'analisi di complessità è un metodo formale per prevedere le risorse richieste dall'algoritmo (cioè il tempo di esecuzione e la quantità di memoria utilizzata).

## Output

* $S\left(n\right)$: memoria richiesta
* $T\left(n\right)$: tempo di esecuzione

## Classificazione degli algoritmi per complessità (dal meno complesso al più complesso)

* costante: $1$
* logaritmico: $\log {n}$
* lineare: $n$
* linearitmico: $n\log {n}$
* quadratico: $n^{2}$
* cubico: $n^{3}$
* esponenziale: $2^{n}$

## Analisi di complessità di caso peggiore

L'analisi di complessità è detta:
* asintotica se il numero di dati tende a infinito;
* di caso peggiore se il tempo stimato non può che essere maggiore o uguale al tempo effettivo su uno specifico dato.
Si stima il caso peggiore perché è quello più frequente generalmente, e perché il caso medio spesso è difficile da calcolare o coincide con il peggiore.

### Ricerca sequenziale

    $T\left(n\right)\propto n$

### Ricerca dicotomica

Bisogna considerare il caso peggiore: la chiave non si trova. Alla i-esima iterazione, la lunghezza del sottovettore è uguale a ${\tfrac {1}{2^{i}}}$. La terminazione avviene quando il vettore è lungo $1={\tfrac {1}{2^{i}}};\;i=\log _{2}{n}$.

### Insertion sort

Nel caso peggiore, ad ogni iterazione del ciclo esterno si fanno i − 1 scansioni del vettore, e all'ultima se ne fanno n − 1:
    $T\left(n\right)=1+2+\ldots +\left(n-2\right)+\left(n-1\right)={\frac {n\left(n-1\right)}{2}}\rightarrow T\left(n\right)\propto n^{2}$

## Notazioni
### O grande ($O$)

    $T\left(n\right)=O\left(g\left(n\right)\right)\Leftrightarrow \exists c>0,\,n_{0}>0:\forall n\geq n_{0}\rightarrow 0\leq T\left(n\right)\leq c\cdot g\left(n\right)$
$g\left(n\right)$ è un limite superiore lasco:
* superiore: è una funzione maggiorante, a partire da un certo $n_{0}$;
* lasco: non scresce come $g\left(n\right)$, ma al più come $g\left(n\right)$.
Se $T\left(n\right)$ è un polinomio in $n$ di grado $m$ → $T\left(n\right)=O\left(n^{m}\right)$.

### Omega grande ($\Omega$)

    $T\left(n\right)=\Omega \left(g\left(n\right)\right)\Leftrightarrow \exists c>0,\,n_{0}>0:\forall n\geq n_{0}\rightarrow 0\leq c\cdot g\left(n\right)\leq T\left(n\right)$
$g\left(n\right)$ è il limite inferiore lasco della complessità asintotica di caso peggiore (≠ caso migliore). Se si dimostra che, per una certa operazione, la $\Omega$ è maggiore della complessità lineare, non si potrà mai trovare un algoritmo lineare che svolga quell'operazione.
$T\left(n\right)$ polinomio → $T\left(n\right)=\Omega \left(n^{m}\right)$

### Theta grande ($\Theta$)

    $T\left(n\right)=\Theta \left(g\left(n\right)\right)\Leftrightarrow \exists c_{1},\,c_{2}\,n_{0}>0:\forall n\geq n_{0}\rightarrow 0\leq c_{1}\cdot g\left(n\right)\leq T\left(n\right)\leq c_{2}\cdot g\left(n\right)$
$g\left(n\right)$ è il limite asintotico stretto di $T\left(n\right)$: $T\left(n\right)$ cresce come $g\left(n\right)$.
È la combinazione dei due precedenti:
* $T\left(n\right)$ polinomio → $T\left(n\right)=\Theta \left(n^{m}\right)$;
* $T\left(n\right)=\Theta \left(g\left(n\right)\right)\leftrightarrow T\left(n\right)=O\left(g\left(n\right)\right)\wedge T\left(n\right)=\Omega \left(g\left(n\right)\right)$

## Online connectivity

L'online connectivity è un problema avente per input un insieme di coppie di interi p e q (per es. i nodi di una rete). (p, q) definisce una relazione di connessione tra i nodi p e q.

### Proprietà

* commutativa: se p è connesso con q → q è connesso con p;
* transitiva: se p è connesso con q ∧ q è connesso con r → p è connesso con r.
Le coppie possono essere:
* mantenute: la connessione della coppia non è ancora nota (output: coppia (p, q));
* scartate: la coppia è già connessa, anche per la proprietà transitiva o commutativa (output: nullo).

### Applicazioni

* reti di computer: ottimizzazione togliendo le connessioni ridondanti;
* reti elettriche;
* linguaggi di programmazione: variabili equivalenti.
La struttura dati a grafo è costituita da 2 insiemi: nodi p e q e archi.
Per ottimizzare il grafo, si verifica di volta in volta se la connessione della coppia in input non è ancora nota o se è implicata già dalle precedenti. L'analisi di questo genere presuppone l'esistenza del grafo → non è un'analisi di connettività online.
La connettività si dice online se si sta lavorando non su una struttura o su un modello pre-esistente, ma su un grafo che viene costruito arco per arco.
* ipotesi: si conoscono i vertici, e ogni vertice è connesso solo a se stesso → nessun arco;
* operazione find (ricerca): a ogni coppia in input, verifica se p e q appartengono allo stesso insieme (2 find);
* operazione union (unione): se p e q non erano connessi, unisci l'insieme a cui appartiene p (S$_p$) e l'insieme a cui appartiene q (S$_q$).
L'online connectivity può essere implementata tramite vettori:
* quick-find: find rapide, union lente;
* quick-union: find lente, union rapide.

### Quick-find

A seconda del contenuto della cella del vettore:
* se è il suo stesso indice i: il vertice i-esimo è connesso a se stesso;
* se è un altro indice: i due vertici appartengono allo stesso insieme.

#### Complessità

* find: accesso a una cella di vettore tramite il suo indice: $O\left(1\right)$
* union: scansione del vettore per cambiare da p a q: $O\left(n\right)$
Complessità di caso peggiore totale: numero di coppie × dimensioni vettore (n)
riferimenti diretti (nessuna catena) → si trova subito il rappresentante

### Quick-union

C'è una catena di riferimenti di tipo indiretto. A seconda del contenuto della cella del vettore:
* se è uguale al suo indice i: fine catena;
* se è diverso dal suo indice: passa alla cella i-esima a cui punta: id[id[...id[i]]...] = (id[i])*

#### Complessità

* find: due elementi sono connessi se (id[i])* = (id[j])*: $T\left(n\right)=O\left(n\right)$
* union: la testa della prima catena punta alla testa della seconda, cioè (id[p])* = (id[q])* → l'albero si frastaglia: $T\left(n\right)=O\left(1\right)$
Nella find si deve perciò percorrere tutta la catena fino alla testa, la union è immediata (unione solo delle teste).