|
L'algoritmo di ricerca sequenziale
Function Ricerca(V: Vettore; N: Integer; K: Elemento): Integer;
Var
I: Integer;
Begin
I:=1; (1)
While (I <= N) And (V[I] <> K) do (2) (3) (4)
I:=I+1; (5) (6)
If(I > N) then (7)
Ricerca:=0 (8)
Else
Ricerca:=I; (9)
End;
Ci sono operazioni di
 | Assegnamento: (1) (5) (8) (9) |
| Confronto: (2) (4) (7) |
| Aritmetico-logiche: (3) (6) |
ognuna delle quali chiede alla CPU tempi diversi; per semplificare decidiamo di trascurare queste differenze e di considerarle tutte equivalenti a un unico tempo d'esecuzione. Allora possiamo concludere che il tempo richiesto alla CPU da questa funzione è (con x = numero di volte che viene eseguito il ciclo while..do) T = T1+[T2+T3+T4+T5+T6]x+(T2+T3+T4)+T7+T8|9 = 6+5x
I valori assunti da T sono
| Vettore vuoto: T1+(T2+T3+T4)+T7+T8 = 3+3 = 6 |
| Elemento in 1° posizione: T1+(T2+T3+T4)+T7+T9 = 3+3 = 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)+(T2+T3+T4+T5+T6)+(T2+T3+T4)+T7+T9 = 6+5*2 = 16 |
| ... |
| Elemento in ultima posizione: 6+5(n-1) |
| Elemento non presente: 6+5n |
Caso ottimo
| Vettore vuoto, elemento in 1° posizione: T = 6 |
Caso pessimo
| Elemento non presente: T = 6+5n |
Caso medio (con posizione da 1 a n)
| T = 1/n*[6+(6+5)+(6+10)+...+6+5(n-1)] = 1/n*[6n+5(n-1)n/2] = 6+5(n-1)/2 = 3.5+2.5n = c1+c2n |
Il tempo richiesto è, tranne che nei casi banali, una funzione lineare della dimensione del vettore n | 
