Algoritmi/L'analisi di complessità degli algoritmi
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). 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
- : memoria richiesta
- : tempo di esecuzione
- Classificazione degli algoritmi per complessità (dal meno complesso al più complesso)
- costante:
- logaritmico:
- lineare:
- linearitmico:
- quadratico:
- cubico:
- esponenziale:
Analisi di complessità di caso peggiore
modificaL'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
- Ricerca dicotomica
Bisogna considerare il caso peggiore: la chiave non si trova. Alla i-esima iterazione, la lunghezza del sottovettore è uguale a . La terminazione avviene quando il vettore è lungo .
- 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:
Notazioni
modificaO grande ( )
modificaè un limite superiore lasco:
- superiore: è una funzione maggiorante, a partire da un certo ;
- lasco: non scresce come , ma al più come .
Se è un polinomio in di grado → .
Omega grande ( )
modificaè il limite inferiore lasco della complessità asintotica di caso peggiore (≠ caso migliore). Se si dimostra che, per una certa operazione, la è maggiore della complessità lineare, non si potrà mai trovare un algoritmo lineare che svolga quell'operazione.
polinomio →
Theta grande ( )
modificaè il limite asintotico stretto di : cresce come .
È la combinazione dei due precedenti:
- polinomio → ;
Online connectivity
modificaL'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 (Sp) e l'insieme a cui appartiene q (Sq).
L'online connectivity può essere implementata tramite vettori:
- quick-find: find rapide, union lente;
- quick-union: find lente, union rapide.
Quick-find
modificaA 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:
- union: scansione del vettore per cambiare da p a q:
Complessità di caso peggiore totale: numero di coppie × dimensioni vettore (n)
riferimenti diretti (nessuna catena) → si trova subito il rappresentante
Quick-union
modificaC'è 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])*
: - union: la testa della prima catena punta alla testa della seconda, cioè
(id[p])* = (id[q])*
→ l'albero si frastaglia:
Nella find si deve perciò percorrere tutta la catena fino alla testa, la union è immediata (unione solo delle teste).