Individuare la posizione di un certo elemento all’interno di una sequenza data.
![](https://www.valcon.it/pp/wp-content/uploads/rs.png)
Posizione di un valore k all’interno di un array v
Function Posizione(V: Vettore; N: Integer; K: Real): Integer;
Var
i, Risp: Integer;
Begin
Risp:=0;
For i:=1 to N do
If(V[i] = K) Then
Risp:=i;
Posizione:=Risp;
End;
Restituisce la posizione dell’ultimo valore presente…
Posizione di un elemento (la prima…)
Function Posizione(V: Vettore; N: Integer; K: Real): Integer;
Var
i, Risp: Integer;
Begin
i:=1;
Risp:=0;
While(i <= N) And (Risp = 0) Do
Begin
If(V[i] = K) Then
Risp:=i;
i:=i+1;
End;
Posizione:=Risp;
End;
Semplifico il ciclo
Function Posizione(V: Vettore; N: Integer; K: Real): Integer;
Var
i: Integer;
Begin
i:=1;
While(i <= N) And (V[i] <> K) Do
i:=i+1;
If(i > N) Then
Posizione:=0
Else
Posizione:=i;
End;
La ricerca sequenziale effettua una scansione dell’array finché non trova il valore richiesto, se presente, o l’array finisce.
Se l’array è ordinato e l’elemento non compare la ricerca sequenziale può essere interrotta se l’elemento esaminato è maggiore di quello cercato
Function Posizione(V: Vettore; N: Integer; K: Real): Integer;
Var
i: Integer;
Begin
i:=1;
While(i <= N) And (V[i] < K) Do
i:=i+1;
If(i > N) Or (V[i] > K) Then
Posizione:=0
Else
Posizione:=i;
End;
Complessità dell’algoritmo
Analisi della complessità, in tempo e asintotica, dell’algoritmo di ricerca sequenziale.
Il codice analizzato è il seguente
Function ricercaSequenziale(V: Vettore; N: Integer; K: Real): 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 *)
ricercaSequenziale:=0 (* 8 *)
Else
ricercaSequenziale:=i; (* 9 *)
End;
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 è
T = T1+(T2+T3+T4+T5+T6)*x+(T2+T3+T4)+T7+T8|9
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 T = 6+5x
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
oppure se occupa l’ultima posizione… - Caso medio, supponiamo di effettuare n ricerche con l’elemento presente alle diverse posizioni: T = 3.5+2.5n
Conclusioni
Il tempo richiesto dall’algoritmo di ricerca sequenziale è, tranne che nei casi banali, una funzione lineare di n, il numero di elementi presenti nel vettore: T(n) = c1+c2n
I valori delle due costanti c1 e c2 sono modesti e comunque poco significativi.
I calcoli per il caso medio
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
Osserva: 1+2+...n = n(n+1)/2