有什么区别或分开O(log(n))和O(n)？

Question

这是我给出的代码,但我无法确定它是O(log(n))还是O(n).

int i=n;
while (i > 0) {  
   i/=2;  
}     

Answer 1

让我们假设n = 1000.

它要经过多少次迭代i = 0？

每次除以2.所以我们将得到下表:

Iteration |   i
----------|--------
    0     |  1000
    1     |  500
    2     |  250
   ...    |  ...
   ...    |  ...
    10    |   0  <-- Here we stop

这有助于您弄清楚复杂性吗？(它应该 - 提示:什么是~log(1000)以及O(n)是什么意思？)