为什么代码的时间复杂度是O(log n)？

Question

这是 Gayle Laakmann 所著的《Cracking the 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)\n{\n    sum += n % 10;\n    n /= 10;\n}\n

\n\n

那么，这个 while 循环需要多少步才能n达到0？您在每一步中所做的事情都n除以10。所以，你需要做k很多次才能达到0。注意，k 是 中的位数n。

\n\n

让我们一步一步进行：\n第一步是当 时，n > 0除以。如果仍为正数，则将其除以。你得到的是或。第三次之后，就到了。k 次之后，它. 循环将结束。但这不是数学意义上的，因为我们处理的是整数。你真正拥有的是 ，在哪里。n10n10n/10/10n / (10^2)n / (10^3)n/(10^k) = 000|n|/(10^k) < 1k\xe2\x88\x88N

\n\n

所以，我们现在有这个：

\n\n

n/(10^k) < 1\nn < 10^k\nlogn < k\n

\n\n

顺便提一句。其也n/(10^(k-1)) > 1，故其：

\n\n

k-1 < logn < k。（顺便说一句，别忘了，这是基础10）。

\n\n

因此，您需要执行logn + 1一些步骤才能完成循环，这就是O(log(n)).

\n