Ricerca sequenziale

di

Individuare la posizione di un certo elemento all’interno di una sequenza data.

L’algoritmo è illustrato con una codifica Pascal

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 che
1+2+...n=n(n+1)/2