Visualizza wikitesto di Algoritmi/L'analisi di complessità degli algoritmi

{{Algoritmi}}
L<nowiki>'</nowiki>'''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). Un algoritmo meno complesso su una macchina più lenta può essere più veloce.

* 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

;Classificazione degli algoritmi per complessità <span style="font-weight: normal">(dal meno complesso al più complesso)</span>
* 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==
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
:<math>T\left(n\right) \propto n</math>

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

;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==
===O grande (<math>O</math>)===
:<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>.

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>)===
:<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.

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

===Theta grande (<math>\Theta</math>)===
:<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>.

È 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==
L<nowiki>'</nowiki>'''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.

# <span style="text-decoration: underline">ipotesi:</span> 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<sub>p</sub>'') e l'insieme a cui appartiene ''q'' (''S<sub>q</sub>'').

L'online connectivity può essere implementata tramite vettori:
* '''quick-find:''' find rapide, union lente;
* '''quick-union:''' find lente, union rapide.

===Quick-find===
[[File:Quick-find.png|thumb|400px]]

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à
* <span style="text-decoration: underline">find:</span> accesso a una cella di vettore tramite il suo indice: <math>O\left(1\right)</math>
* <span style="text-decoration: underline">union:</span> 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'')

riferimenti diretti (nessuna catena) → si trova subito il rappresentante
{{clear|right}}
===Quick-union===
[[File:Quick-union.png|thumb|300px]]

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: <code>id[id[...id[''i'']]...] = (id[''i''])*</code>

;Complessità
* <span style="text-decoration: underline">find:</span> due elementi sono connessi se <code>(id[''i''])* = (id[''j''])*</code>: <math>T\left(n\right) = O\left(n\right)</math>
* <span style="text-decoration: underline">union:</span> la testa della prima catena punta alla testa della seconda, cioè <code>(id[''p''])* = (id[''q''])*</code> → 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).
[[Categoria:Algoritmi|{{SUBPAGENAME}}]]