Analisi della complessità, in tempo e asintotica, dell’algoritmo di ricerca sequenziale. Il codice analizzato è il seguente
public int ricerca(double[] v, double k)
{
int i=0; // 1
while(i < v.length) && (v[i] != k) // 2, 3, 4
i=i+1; // 5, 6
if(i == v.length) // 7
return -1; // 8
else
return i; // 9
}
presenta operazioni di
- assegnamento: 1, 5, 8, 9
- confronto: 2, 4, 7
- aritmetico-logiche: 3, 6
Il tempo totale richiesto da questo sottoprogramma alla CPU è
con
- (T2+T3+T4+T5+T6), le operazioni svolte ad ogni passo del While
- x, il numero di volte che viene eseguito il While (da 0 a n)
- (T2+T3+T4), quando K viene individuato alla posizione i-esima oppure il vettore finisce
- T8|9, una delle due istruzioni finali
Per semplificare i calcoli si decide di trascurare le differenze esistenti tra i tempi di esecuzione delle diverse operazioni e di stabilire un tempo costante per tutte, allora
I valori effettivi di T sono
- vettore vuoto: T1+(T2+T3+T4)+T7+T8 = 6
- elemento in 1° posizione: T1+(T2+T3+T4)+T7+T9 = 6
- elemento in 2° posizione: T1+[T2+T3+T4+T5+T6]+(T2+T3+T4)+T7+T9 = 6+5*1 = 11
- elemento in 3° posizione: T1+[T2+T3+T4+T5+T6]*2+ ... = 6+5*2 = 16
- ...
- elemento in ultima posizione: 6+5*(n-1)
- elemento non presente: 6+5n
Analizziamo i casi più interessanti
- Caso ottimo, quando il vettore è vuoto oppure l'elemento K compare in 1° posizione: T=6
- Caso pessimo, se l'elemento K non è presente: T=6+5n
- Caso medio, supponiamo di effettuare n ricerche con l'elemento presente alle diverse posizioni: T=3.5+2.5n
Conclusioni
Il tempo richiesto è, tranne che nei casi banali, una funzione lineare di n, il numero di elementi presenti nel vettore
I valori delle due costanti c1 e c2 sono modesti e comunque poco significativi.
T=[(6+5*0)+(6+5*1)+(6+5*2)+...+(6+5(n-1))]/n
=[6n+5(1+2+...+n-1)]/n
=[6n+5(n-1)*n/2]/n
=6+5(n-1)/2
=6+5/2*n-5/2
=7/2+5/2*n
=3.5+2.5*n