Confronto tra ricerche
Ipotizzando, pessimisticamente, 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
| 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!La complessità dell'algoritmo di ricerca binaria
O(log n)
è profondamente diversa da quello di ricerca sequenziale
O(n).
