Quelle est la différence entre O(log(n)) et O(n) ?

Question

C'est le code que l'on m'a donné mais je n'arrive pas à décider si c'est O(log(n)) ou O(n).

int i=n;
while (i > 0) {  
   i/=2;  
}

Answer 1

Supposons que n = 1000 .

Combien d'itérations cela prendra-t-il jusqu'à ce que i = 0 ?

À chaque fois, on le divise par 2. On obtient donc le tableau suivant :

Iteration |   i
----------|--------
    0     |  1000
    1     |  500
    2     |  250
   ...    |  ...
   ...    |  ...
    10    |   0  <-- Here we stop

Cela vous aide-t-il à comprendre la complexité ? (Cela devrait - Indice : que signifie ~log(1000) et que signifie O(n) ?)