Sto imparando i tempi di esecuzione della notazione Big O e i tempi ammortizzati. Capisco la nozione di O(n) tempo lineare, che significa che la dimensione dell'input influisce proporzionalmente sulla crescita dell'algoritmo...e lo stesso vale, per esempio, per il tempo quadratico O(n2) ecc..anche algoritmi, come i generatori di permutazione, con O(n!) tempi, che crescono per fattoriali.
Per esempio, la seguente funzione è O(n) perché l'algoritmo cresce in proporzione al suo input n:
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
Allo stesso modo, se ci fosse un ciclo annidato, il tempo sarebbe O(n2).
Ma cos'è esattamente O(log n)? Per esempio, cosa significa dire che l'altezza di un albero binario completo è O(log n)?
So (forse non molto dettagliatamente) cos'è il logaritmo, nel senso che: log10 100 = 2, ma non riesco a capire come identificare una funzione con un tempo logaritmico.
Il tempo di esecuzione logaritmico (O(log n)
) significa essenzialmente che il tempo di esecuzione cresce in proporzione al logaritmo della dimensione dell'input - per esempio, se 10 elementi richiedono al massimo una certa quantità di tempo x
, e 100 elementi richiedono al massimo, diciamo, 2x
, e 10.000 elementi richiedono al massimo 4x
, allora sembra una complessità temporale O(log n)
.
Significa semplicemente che il tempo necessario per questo compito cresce con log(n) (esempio: 2s per n = 10, 4s per n = 100, ...). Leggete gli articoli di Wikipedia su Binary Search Algorithm e Big O Notation per ulteriori precisazioni.