为什么代码O（log n）的时间复杂度？

下面是Gayle Laakmann编写的“破解编码访问”一书中给出的代码。在此时刻的代码的复杂性找到： -为什么代码O（log n）的时间复杂度？

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

我知道时间复杂度应为n个位数。根据该书，其运行时间复杂度为O（log n）。本书提供了简要描述，但我不明白。

来源

2017-10-07 rani rawat

n中的位数是log n。（或者O复杂度近似接近。） –

n不减1，所以不是线性的。在循环中的每次传递，n减少一个数量级 – Tim

[代码复杂度]的可能的重复（https://stackoverflow.com/questions/39797459/code-complexity） –

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

，是多少步骤将这个while循环采取使n来0？你在每一步中所做的事情，将n与10分开。所以，你需要做到这一点k次，以达到0。请注意，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。

所以，我们现在有这样的：

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))。

来源

2017-10-07 17:08:54

感谢Adnan为这个完美的答案。 –

逻辑运行的次数是log（n）到10的基数，它等于（log（n）到基2）/ log（10）到2）的基数。就时间复杂度而言，这只是O（log（n））。请注意，以10为底的log（n）是您如何表示n中的位数。

来源

2017-10-22 17:04:24

为什么代码O（log n）的时间复杂度？

回答

相关问题