Algoritmi e programmazione/L'analisi di complessità degli algoritmi

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 2. L'analisi di complessità degli algoritmi.

[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/L'analisi di complessità degli algoritmi}}/Gli algoritmi{{#ifcategory:Traduzioni\|/L'analisi di complessità degli algoritmi\|\|/L'analisi di complessità degli algoritmi}}\|1. Gli algoritmi]]	[[{{#ifcategory:Traduzioni\|/L'analisi di complessità degli algoritmi\|Algoritmi e programmazione\|/L'analisi di complessità degli algoritmi}}\|{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/L'analisi di complessità degli algoritmi}}]]	[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/L'analisi di complessità degli algoritmi}}/Gli algoritmi di ordinamento{{#ifcategory:Traduzioni\|/L'analisi di complessità degli algoritmi\|\|/L'analisi di complessità degli algoritmi}}\|3. Gli algoritmi di ordinamento]]

2 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).

Il tempo però non è un tempo fisico o misurato sperimentalmente su un processore, ma dipende dal numero di passi → l'analisi di complessità è indipendente dalla macchina. Si assume che la macchina lavori in modo sequenziale e non parallelo (architettura di Von Neumann). 8 Un algoritmo meno complesso su una macchina più lenta può essere più veloce.

3 L'analisi è indipendente da quali dati in ingresso ci sono ma è dipendente solo da quanti dati in ingresso ci sono, cioè più in generale dalla dimensione n del problema.

Output

<math>S \left(n\right)</math>: memoria richiesta
<math>T \left(n\right)</math>: tempo di esecuzione

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

costante: <math>1</math>
logaritmico: <math>\log{n}</math>
lineare: <math>n</math>
linearitmico: <math>n \log{n}</math>
quadratico: <math>n^2</math>
cubico: <math>n^3</math>
esponenziale: <math>2^n</math>

Analisi di complessità di caso peggiore[modifica | modifica sorgente]

5 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.

6 Si stima il caso peggiore perché è quello più frequente generalmente, e perché il caso medio spesso è difficile da calcolare o coincide con il peggiore.

9 Ricerca sequenziale: <math>T\left(n\right) \propto n</math>

10 Ricerca dicotomica

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

11 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:

<math>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</math>

Notazioni[modifica | modifica sorgente]

O grande (<math>O</math>)[modifica | modifica sorgente]

13 <math>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)</math>

<math>g\left(n\right)</math> è un limite superiore lasco:

superiore: è una funzione maggiorante, a partire da un certo <math>n_0</math>;
lasco: non scresce come <math>g\left(n\right)</math>, ma al più come <math>g\left(n\right)</math>.

14 Se <math>T\left(n\right)</math> è un polinomio in <math>n</math> di grado <math>m</math> → <math>T\left(n\right) = O\left(n^m\right)</math>.

Omega grande (<math>\Omega</math>)[modifica | modifica sorgente]

15 <math>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)</math>

<math>g\left(n\right)</math> è il limite inferiore lasco della complessità asintotica di caso peggiore (≠ caso migliore). Se si dimostra che, per una certa operazione, la <math>\Omega</math> è maggiore della complessità lineare, non si potrà mai trovare un algoritmo lineare che svolga quell'operazione.

16 <math>T\left(n\right)</math> polinomio → <math>T\left(n\right) = \Omega \left( n^m \right)</math>

Theta grande (<math>\Theta</math>)[modifica | modifica sorgente]

17 <math>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)</math>

<math>g\left(n\right)</math> è il limite asintotico stretto di <math>T\left(n\right)</math>: <math>T\left(n\right)</math> cresce come <math>g\left(n\right)</math>.

18 È la combinazione dei due precedenti:

<math>T\left(n\right)</math> polinomio → <math>T\left(n\right) = \Theta\left(n^m\right)</math>;
<math>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)</math>

Online connectivity[modifica | modifica sorgente]

19 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).

20 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.

21 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.

34 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.

35 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[modifica | modifica sorgente]

37 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.

38 Complessità

find: accesso a una cella di vettore tramite il suo indice: <math>O\left(1\right)</math>
union: scansione del vettore per cambiare da p a q: <math>O\left(n\right)</math>

Complessità di caso peggiore totale: numero di coppie × dimensioni vettore (n)

39 riferimenti diretti (nessuna catena) → si trova subito il rappresentante

Quick-union[modifica | modifica sorgente]

53 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])*

55 Complessità

find: due elementi sono connessi se (id[i])* = (id[j])*: <math>T\left(n\right) = O\left(n\right)</math>
union: la testa della prima catena punta alla testa della seconda, cioè (id[p])* = (id[q])* → l'albero si frastaglia: <math>T\left(n\right) = O\left(1\right)</math>

Nella find si deve perciò percorrere tutta la catena fino alla testa, la union è immediata (unione solo delle teste).