Pourquoi la complexité en temps du code O (log n) est-elle importante?

Question

Voici le code donné dans le livre "Cracking the Coding Interview" par Gayle Laakmann. Ici, la complexité temporelle du code pour trouver: -

int sumDigits(int n) 
{ int sum=0; 
while(n >0) 
{ 
    sum+=n%10; 
    n/=10 
} 
return sum ; 
} 

Je sais la complexité du temps devrait être le nombre de chiffres n. Selon le livre, sa complexité d'exécution est O (log n). Livre fourni une brève description, mais je ne comprends pas.

Answer 1

while(n > 0) 
{ 
    sum += n % 10; 
    n /= 10; 
} 

, comment cela va-t pas prendre de boucle while pour que n vient à 0? Ce que vous faites dans chaque étape, vous divisez n avec 10. Donc, vous devez le faire k fois afin de parvenir à 0. Notez, k est le nombre de chiffres dans n.

Lets go étape par étape: La première étape est quand n > 0, vous divisez par n10. Si n est toujours positif, vous allez le diviser par 10. Ce que vous obtenez là est n/10/10 ou n/(10^2). Après la troisième fois, c'est n/(10^3). Et après k fois, c'est n/(10^k) = 0. Et la boucle va se terminer. Mais ce n'est pas 0 dans le sens mathématique, c'est 0 parce que nous traitons des nombres entiers. Ce que vous avez vraiment est |n|/(10^k) < 1, où k∈N.

Donc, nous avons maintenant:

n/(10^k) < 1 
n < 10^k 
logn < k 

btw. c'est aussi n/(10^(k-1)) > 1, donc c'est:

k-1 < logn < k. (N'oubliez pas, c'est la base 10). Donc, vous devez faire logn + 1 étapes afin de terminer la boucle, et c'est pourquoi O(log(n)).

Answer 2

Le nombre de fois que la logique s'exécute est log (n) à la base de 10 qui est identique à (log (n) à la base 2)/log (10) à la base de 2). En termes de complexité temporelle, ce serait simplement O (log (n)). Notez que log (n) à la base de 10 est comment vous représenter le nombre de chiffres dans n.