Complessità delle ricerche
Ricerca binaria
L'algoritmo
FUNZIONE binaria(IN REALE v[], IN REALE k): INTERO
INIZIO
INTERO risp=-1,
inf=0,
sup=v.QUANTI-1,
medio
MENTRE(inf <= sup AND risp == -1)
INIZIO
medio=(inf+sup)/2
SE(v[medio] < k) ALLORA
inf=medio+1
ALTRIMENTI SE(v[medio] == k) ALLORA
risp=medio
ALTRIMENTI
sup=medio-1
FINE
binaria=risp;
FINE
INIZIO
INTERO risp=-1,
inf=0,
sup=v.QUANTI-1,
medio
MENTRE(inf <= sup AND risp == -1)
INIZIO
medio=(inf+sup)/2
SE(v[medio] < k) ALLORA
inf=medio+1
ALTRIMENTI SE(v[medio] == k) ALLORA
risp=medio
ALTRIMENTI
sup=medio-1
FINE
binaria=risp;
FINE
Utilizzando la tecnica di calcolo della complessità in tempo possiamo concludere che
T(x) = c1+c2x
con x il numero di volte che viene eseguito il ciclo.I calcoli approssimati per T danno
- vettore vuoto: ~8
- elemento trovato al 1° passo (in mezzo): c1+c2*1
- elemento trovato al 2° passo: c1+c2*2
- ...
- elemento trovato all'ultimo passo: c1+c2*(m-1)
- elemento non presente: c1+c2*m
Supponiamo pessimisticamente di dover aspettare sempre fino all'ultimo passo, allora
T(n)=c1+c2*m.
Caso pessimo
Quanto vale m? La dimensione del vettore sul quale si effettua la ricerca passo-passo è- n
- ~n/2
- ~n/4
- ~n/8
- ...
- 1
- 0
Quando il valore della potenza di 2 a denominatore raggiunge n il ciclo termina sicuramente, cioè per
2m=n
quindi, nel caso pessimo
T(n) = c1+c2m = c1+c2log2n
Esempi numerici
| n | m |
|---|---|
| 24 = 16 | 4 |
| 28 = 256 | 8 |
| 210 = 1.024 | 10 |
| 216 = 65.536 | 16 |
| 220 = 1.048.576 | 20 |
| 230 = 1.073.741.824 | 30 |
