Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

ComplessitÓ delle ricerche

Precedente
SUPERIORE
Successiva

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

bulletAssegnamento: (1) (5) (8) (9)
bulletConfronto: (2) (4) (7)
bulletAritmetico-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

bulletVettore vuoto: T1+(T2+T3+T4)+T7+T8 = 3+3 = 6
bulletElemento in 1░ posizione: T1+(T2+T3+T4)+T7+T9 = 3+3 = 6
bulletElemento in 2░ posizione: T1+(T2+T3+T4+T5+T6)+(T2+T3+T4)+T7+T9 = 6+5*1 = 11
bulletElemento in 3░ posizione: T1+(T2+T3+T4+T5+T6)+(T2+T3+T4+T5+T6)+(T2+T3+T4)+T7+T9 = 6+5*2 = 16
bullet...
bulletElemento in ultima posizione: 6+5(n-1)
bulletElemento non presente: 6+5n

Caso ottimo

bulletVettore vuoto, elemento in 1░ posizione: T = 6

Caso pessimo

bulletElemento non presente: T = 6+5n

Caso medio (con posizione da 1 a n)

bulletT = 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

ComplessitÓ delle ricerche - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Precedente
SUPERIORE
Successiva