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)
16 5+5*16 = 85 100+100*4 = 500
64 5+5*64 = 325 100+100*6=700
256 5+5*256 = 1.285 100+100*8 = 900
1.024 5+5*1.024 = 5.125 100+100*10 = 1.100
1.048.576 ~5.000.000 100+100*20 = 2.100
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