COMPLESSITÀ LOGARITMICA:  log(n)

La complessità cresce come la lunghezza del numero n.

N. B. 
 Scrittura posizionale:

  1. La lunghezza di un numero, in base due, è pari al logaritmo in base 2, approssimato per eccesso, del numero n. Se il numero è una potenza esatta di due allora la lunghezza è pari al logaritmo in base due del numero aumentato di uno.

            log28 = 3;       la lunghezza di 8 in base due è 3+1       810  = 10002    

            log25 = 2,3...  (viene approssimato a 3)    infatti la lunghezza di 5 in base due è 3       510 = 1012

  1. Se il numero è scritto in base 10, la lunghezza del numero è il logaritmo in base 10 del numero n, aumentato di uno se il numero è una potenza esatta di dieci, approssimato per eccesso se non è una potenza di dieci: Log 1000 = 3,  infatti 1000 ha una lunghezza di quattro cifre, Log 300 = 2,4... infatti  300 ha lunghezza pari a 3 cifre).
  2. La lunghezza di un numero scritto in una base qualunque è pari al logaritmo del numero in quella base, nel senso spiegato nei casi precedenti.

PER CONCLUDERE LA LUNGHEZZA DEL NUMERO CRESCE COME IL LOGARITMO DEL NUMERO

IL COSTO CRESCE COME LA LUNGHEZZA DEL NUMERO, SCRITTO IN UNA QUALUNQU BASE, PERCHÉ NON VIENE FATTO IL CALCOLO ESATTO DI COME CRESCE IL COSTO COMPUTAZIONALE: É SOLAMENTE AFFERMATA UNA TENDENZA, IL COSTO NON CRESCE PIÙ DELLA LUNGHEZZA DEL NUMERO.

ESEMPI:

Ricerca binaria in un insieme ordinato:
 il numero di confronti per cercare  un elemento in un vettore, confrontandolo ad ogni passo con l'elemento che si trova a metà della parte  in cui potrebbe trovarsi l'elemento; cresce come il log2n, dove n è il numero degli elementi.

Se gli elementi sono 250000 allora il numero di confronti necessari è pari      log2250000 = 17,9...,  quindi 18 confronti.

Se gli elementi sono 500000 allora il numero di confronti necessario è pari     log2500000 = 18,9...,  quindi 19 confronti.

Se gli elementi sono 1000000 allora il numero di confronti necessario è pari a     log21000000 = 19,9...,   quindi 20 confronti.

Possiamo concludere che se il log. in base 2 di un numero è cresciuto di una unità, anche il numero di confronti necessari è cresciuto di una unità, quindi raddoppiando il numero degli elementi ci vuole solo 1 confronto in più.