Complessità delle 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
256 5+5*256=1285 100+100*8 = 900
1.024 5+5*1.024=5125 100+100*10 = 1.100
65.536 ~105 100+100*16 = 1.700
1.048.576 ~107 100+100*20 = 2.100
1.073.741.824 ~1010 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

Utilizzando la terminologia della complessità asintotica in tempo si può concludere che

la complessità dell’algoritmo di ricerca binaria, O(log n), è profondamente diversa da quella dell’algoritmo di ricerca sequenziale, O(n).
Notice: This work is licensed under a BY-NC-SA. Permalink: Complessità delle ricerche

Comments are closed.