Informatica 5 Liceo Scientifico Scienze Applicate/Algoritmi Complessità computazionale

Complessità computazionale

In informatica per risolvere i problemi si utilizzano degli algoritmi, dei pezzi di codice che risolvono in modo efficiente una particolare classe di problemi, si parla ad esempio dell'algoritmo dell'ordinamento oppure dell'algoritmo della ricerca dicotomica etc. Quando si va a valutare l'efficienza di un algoritmo la si sintetizza mediante un indice detto ordine della complessità computazionale dell'algoritmo che identifica il numero di operazioni necessarie per risolvere un problema generico con quel particolare algoritmo. Più in generale un algoritmo viene valutato non solo in termini di istruzioni necessarie ma anche per l'utilizzo della memoria.

La lettera O (si legge o grande) indica il grado di complessità, e dopo questo simbolo racchiuso fra parentesi si indica il numero o l'espressione che ci permette di calcolarne il grado.Se si scrive O(3) si intende che il numero di operazioni per eseguire l'algoritmo e' pari a 3, se si scrive O(n) ,con n si intende di solito il numero di elementi caricati in un vettore che devono essere analizzati, si intende che il numero di operazioni è proporzionale alla dimensione del vettore (cioe' al numero di elementi contenuti nel vettpre) se si scrive O(4n) e' come nel caso O(n) ma si e' individuata anche la costante di proporzionalità (4) rispetto al numero di elementi del vettore, se trovate O(n² )te vuol dire che il numero di operazioni segue una legge quadratica rispetto al numero di elementi contenuti nel vettore di dimensione n. Qualche volta il calcolo e' meno precisa se trovate O(1) se i dati sono contenuti in un vettore indica che le operazioni da eseguirsi sono indipendenti dal numero di elementi in un vettore O(log₂n) che le operazioni da eseguirsi seguono una legge logaritmica rispetto al numero di elementi del vettore O(n) operazioni sono proporzionali al numero di elementi contenuti nel vettore

Se gli elementi del vettore sono n un algoritmo molto veloce ha O(k) con k= costante, uno veloce ha un andamento logaritmico, uno normale ha complessita' lineare O(n) oppure O(kn), le cose vanno male se O(nlog₂n) e vanno molto male se le leggi diventano quadratiche o di grado superiore O(n²) O(n³) .

Naturalmente il confronto deve essere fatto su algoritmi diversi che risolvono la stessa classe di problemi. Nella pratica qualche volta è semplice individuare l'ordine di complessità altre volte no, in alcuni casi l'ordine di complessità dipende dai particolari valori contenuti nel vettore, in questo caso si fornisce l'ordine di complessità nel caso peggiore, in una situazione media e nella situazione migliore, in alcuni casi il calcolo diventa difficile e si utilizzano programmi software detti profiler che analizzano i nostri algoritmi in casi reali fornendo informazioni sull'uso della CPU della memoria RAM e del numero di chiamate alle diverse funzioni.State attenti che istruzioni diverse fra loro di un programma richiedono tempi di esecuzione diversi, incrementare una variabile richiede magari un ciclo della cpu, moltiplicare 2 numeri in virgola mobile richiede 100 cicli della cpu. Riassumendo l'ordine di complessita' ci fornisce un parametro sintetico della velocita' di esecuzione dello stesso in funzione del numero di dati da elaborare, se non ci basta l'ordine della complessita' o questo non e' di facile calcolo perché dipende anche dai valori assunti dai dati allora bisogna usare un profiler applicato a specifici casi.

E' possibile trovare il grado di complessità anche su algoritmi quali il bubble sort, la ricerca dicotomica, la somma...etc
La tabella imdica il numero di operazioni da eseguirsi in funzione della dimensione n del vettore e dell'ordine di complessita+

n	O_(1)	O(log2 n)	O(n)	O(nlog2 n)	O(n2)
1	1	1	1	1	1
5	1	2	5	10	25
10	1	3	10	30	100
100	1	7	100	730	10000
1000	1	10	1000	10000	1000000

Molte volte il grado di complessità è semplice da trovare, ecco alcuni esempi:

1° esempio

b=b+1                         
c=c-2
z=c+b

In un algoritmo dove sono presenti solo queste tre operazioni il grado di complessità sarà 3, cioe' O(3)

2° esempio

for i= 1 : n
 istruzione
end

il ciclo for ripete per n volte l'istruzione, l'ordine di complessità sarà pari ad O(n) .

3° esempio

for j= 1 : n
 istruzione1
end
for k= 1 : n
 istruzione2
end

In questo caso l'ordine di complessità sarà 2n, in quanto ci sono due cicli for separati, non nidificati e quindi ciascuno ripete per n volte la propria istruzione O(2n).

4° esempio

for h= 1 : n
 for t= 1 : n
   istruzione1
   istruzione2
   istruzione3
 end
end

Invece in questo caso i cicli for si presentano nidificati e quindi l'ordine di complessità risulterà essere O(3n²).

5° esempio Per quanto riguarda il BubbleSort l'ordine di complessità è un po' più complicato e risulta essere $O({\frac {n^{2}}{2}})$.

Vediamo insieme di giustificarne il valore:

v=[5;-8;3;4]
n=4
for i=2:n
 for j=n:-1:i
   if (v(j)<v(j-1))
    temp=v(j)
    v(j)=v(j-1)
    v(j-1)= temp
   endif
 endfor
endfor

Si può notare come ci siano due for nidificati dove si procederà moltiplicando il numero di ripetizioni del primo ciclo con quelle del secondo.

Nel primo for le iterazioni sono n-1 che però se pensiamo a numeri molto grandi può essere approssimato ad n; il secondo for invece numero di iterazioni che varia ( se il vettore ha 10 elementi, il ciclo for interno ripete l'istruzione if prima per 9 volte, poi per 8, poi per 7, ..., infine per 1) ma che mediamente vale n/2 perché se pensiamo ad una serie di numeri come questa

9  8  7  6  5  4  3  2  1

la media vale 5 e la potete calcolare velocemente osservando che la media del primo elemento con l'ultimo vale 5, del secondo con il penultimo vale 5, del terzo con il terzultimo vale 5 e cosi facendo risulterà sempre la stessa, cioè 5.

Quindi per concludere se moltiplichiamo le n iterazioni del primo for con le n/2 medie del secondo for il grado totale dell'algoritmo sarà $O({\frac {n^{2}}{2}})$.

6° esempio Pensando alla ricerca esaustiva, dove si ricerca un elemento in un vettore non ordinato, bisogna scorrere tutto il vettore una cella alla volta finché non troviamo l'elemento da ricercare. Se quello che cerchiamo è presente nel vettore possiamo essere fortunati e trovarlo nella prima posizione del vettore o possiamo essere sfortunati e trovarlo nella'ultima posizione, mediamente (in senso probabilistico) lo troveremo dopo aver analizzato il 50% del vettore, l'ordine di complessità vale allora $O({\frac {n}{2}})$.
Se invece non è presente dovremo passare in rassegna tutti gli elementi del vettore per essere sicuri che non è presente, in questo caso l'ordine di complessità vale allora $O(n)$.
Quindi la complessità computazionale spesso è legata ai dati contenuti nel vettore e a certe condizione assunte, l'ordine di complessità può avere un valore max che esprime la situazione peggiore e un valore medio.