Complessità: ricerche

Per semplificare i calcoli e per rendere più evidente il confronto tra i due algoritmi ipotizziamo che i coefficienti numerici delle funzioni di complessità in tempo siano molto sfavorevoli per la ricerca binaria, per esempio

  • Tseq(n)=5+5*n
  • Tbin(n)=100+100*log2n

calcoliamo i tempi di attesa al variare di n

n Tseq(n) Tbin(n)
24 = 16 5+5·16 = 85 100+100·4 = 500
26 = 64 5+5·64 = 325 100+100·6 = 700
28 = 256 5+5·256 = 1.285 100+100·8 = 900
210 = 1.024 5+5·1.024 = 5.125 100+100·10 = 1.100
220 = 1.048.576 … > 5.000.000 100+100·20 = 2.100
230 = 1.073.741.824 … > 5.000.000.000 100+100·30 = 3.100

Anche in questa situazione di svantaggio ipotetico l’algoritmo di ricerca binaria si comporta meglio se applicato ad appena 200 elementi!

comp_b2