java - 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) 是什么意思？）