Calcolare la complessità asintotica nel tempo e nello spazio dei seguenti
due algoritmi lsearch e bsearch (Figura ).
Verificare che il secondo (bsearch)
permette di ricercare il nome di una persona in un elenco di un milione
di abitanti con un tempo che è soltanto tre volte maggiore di quello
di un elenco di mille abitanti, mentre con il primo (lsearch)
il tempo richiesto è
volte maggiore.
Suggerimento: per valutare la complessità di bsearch, consideriamo per semplicità
il caso in cui il numero di elementi sia . In questo caso si può vedere che
bsearch, elimina metà degli elementi ad ogni confronto. Per cui, se per esempio
si vuole ricercare il numero 10 all'interno dell'insieme [-2, 0, 3, 4, 5, 10, 12, 30],
si avrà (Tabella
) che il numero massimo di confronti necessari è 3.
Ossia il numero di confronti è pari a
, da cui ne consegue una complessità
computazionale nel caso peggiore pari a
.
-2 | 0 | 3 | 4 | 5 | 10 | 12 | 30 |
-2 | 0 | 3 | 4 | 5 | 10 | 12 | 30 |
-2 | 0 | 3 | 4 | 5 | 10 | 12 | 30 |
-2 | 0 | 3 | 4 | 5 | 10 | 12 | 30 |