FANDOM


Nota disambigua
Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 2. L'analisi di complessità degli algoritmi.
Blue Glass Arrow RTL  1. Gli algoritmiCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  3. Gli algoritmi di ordinamento
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

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.
  • L'analisi è indipendente da quali dati in ingresso ci sono 3 ma è dipendente solo da quanti dati in ingresso ci sono, cioè più in generale dalla dimensione n del problema.
Output
  • S \left(n\right): memoria richiesta
  • T \left(n\right): tempo di esecuzione
4 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 peggioreModifica

L'analisi di complessità è detta:

  • 5 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
T\left(n\right) \propto n
10 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}.

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:

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

NotazioniModifica

O grande (O)Modifica

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

14 Se T\left(n\right) è un polinomio in n di grado mT\left(n\right) = O\left(n^m\right).

Omega grande (\Omega)Modifica

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

16 T\left(n\right) polinomio → T\left(n\right) = \Omega \left( n^m \right)

Theta grande (\Theta)Modifica

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

18 È 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 connectivityModifica

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 qq è connesso con p;
  • transitiva: se p è connesso con rq è connesso con rp è 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.

  1. 35 ipotesi: si conoscono i vertici, e ogni vertice è connesso solo a se stesso → nessun arco;
  2. operazione find (ricerca): a ogni coppia in input, verifica se p e q appartengono allo stesso insieme (2 find);
  3. 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-findModifica

Quick-find

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.
Complessità
  • 38 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)

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

Quick-unionModifica

Quick-union

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])*
Complessità
  • 55 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).

Blue Glass Arrow RTL  1. Gli algoritmiCrystal Clear app kfm home  Algoritmi e programmazioneBlue Glass Arrow  3. Gli algoritmi di ordinamento

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Inoltre su FANDOM

Wiki casuale