Complessità: ricerca binaria

Analizziamo il codice

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: ~7
  • 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.

Quanto vale m?

La dimensione del vettore sul quale si effettua la ricerca passo-passo è

  • n
  • ~n/2
  • ~n/4
  • ~n/8
  • ...
  • 2
  • 1
  • 0

Quando il valore della potenza di 2 a denominatore raggiunge n il ciclo termina sicuramente, cioè per

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

L’algoritmo di ricerca binaria applicato a un vettore con un miliardo di elementi garantisce una risposta dopo appena 30 passi!

Notice: This work is licensed under a BY-NC-SA. Permalink: Complessità: ricerca binaria

Comments are closed.