왜 코드의 시간 복잡도가 O (log n)입니까?

Question

다음은 Gayle Laakmann이 저술 한 "Coding Interview"의 코드입니다. 여기에 코드의 시간 복잡도는 찾을 수 있습니다 : -

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

나는 시간 복잡도를 n의 자릿수해야한다 알고있다.

이 책에 따르면 실행 시간 복잡성은 O (log n)입니다. 책은 간단한 설명을 제공했지만 이해가되지 않습니다.

Answer 1

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

그래서, 얼마나 많은 단계 n는 0이 while 루프의 테이크를 제공 할 수 있도록? 각 단계에서 수행하는 작업은 n을 10으로 나눕니다. 따라서 0으로 가려면 k 번해야합니다. k는 n의 자릿수입니다.

처음 단계는 n > 0 일 때 n을 10으로 나눕니다. n이 여전히 양수이면 10으로 나눕니다. 당신이 얻는 것은 n/10/10 또는 n/(10^2)입니다. 세 번째 시간이 지나면 n/(10^3). 그리고 k 시간 후에, 그 n/(10^k) = 0. 그리고 루프가 끝납니다. 그러나 이것은 수학적 의미에서 0이 아니며, 우리가 정수를 다루기 때문에 0입니다. 실제로 가지고있는 것은 |n|/(10^k) < 1입니다. 여기에서 k∈N입니다.

그래서 우리는 지금이 있습니다 Btw는

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

. 그것의 n/(10^(k-1)) > 1, 그래서 그것의 것 :

k-1 < logn < k. (btw. 잊지 마세요. 이것은 10입니다).

루프를 완료하려면 logn + 1 걸음을 수행해야합니다. 그 이유는 O(log(n))입니다.

Answer 2

로직이 실행되는 횟수는 log (n)에서 10의 기수까지입니다. 이는 (2 기수에 대한 log (n)/log (10)에서 2의 기수까지와 동일합니다). 시간 복잡성의 측면에서 이것은 단순히 O (log (n)) 일 것입니다. log (n)을 10의 밑수로 설정하면 n의 자릿수를 어떻게 표현할 수 있습니다.