大O表示法-请解释O（log2n）

Question

我很难理解为什么这段代码的时间复杂度是O(log 2^n):

for (int i = n; i>=1; i=i/2){
    sum = i+j;
}

我原本以为时间复杂度是O(n)。

- sukiyo

---

哪一部分让你感到困惑？注意 i = i / 2 这一行代码了吗？ - Elliott Frisch

@ElliottFrisch，我看到了这个for循环，我认为它只是O(n)。我不明白在for循环中i = i / 2的意义。我知道i被2除（在每个for循环中都被除以2吗？）。 - sukiyo

@sukiyo：每次循环都将i除以2，因此如果i从1024开始，则为512、256、128、64、32、16、8、4、2、1，然后是0（由于整数除法），此时循环退出。因此，每次将n加倍，您将在循环退出之前获得1个更多的迭代。这就是log (base 2) of n的定义。 - StriplingWarrior

Answer 1

这是O(log_2 n)。因为它将一直运行，直到n变成1。

在第k步之后，假设整个事情都变成1。

所以n/2^k = 1

k=log_2 n

复杂性为O(log_2 n)

- user2736738

---

n/2^k 是 i=i/2 的部分吗？ - sukiyo

@sukiyo：没错，在每一步中，你基本上都是将n除以2。你理解得很对。 - user2736738

“where did it go means?”的意思是什么？在每次迭代中，n的值（存储在i中）会减少...就像首先i=n，然后i=n/2，然后i=n/4，然后i=n/8...。 - user2736738

@sukiyo 是的，它是以 2 为底的 log_2 n。 - user2736738

我认为使用“lg n”或“log2 n”符号更清晰。Log表示以10为底的对数。Ln表示以e为底的对数。 - Gurwinder Singh

Answer 2

简短回答：

如@coderredoc所解释的，此代码片段的时间复杂度为O(log n)。在渐进符号中，对数的底数是不重要的，因为它只会影响常数。

深入回答：

如果这是在学术背景下提出的问题，则请详细了解大O符号和大Θ符号之间的区别。 http://web.mit.edu/16.070/www/lecture/big_o.pdf https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation 对于您特定的问题，任何时间复杂度为O(log n)的代码都可以理论上说成是O(2^n)、O(n)或O(log 2^n)。因为，大O符号描述的是上界，而不是紧密界限。

- Yogi Devendra