algorithm - fun() 的时间复杂度？

Question

我正在通过这个问题来计算时间复杂度。

int fun(int n)
{
  int count = 0;
  for (int i = n; i > 0; i /= 2)
     for (int j = 0; j < i; j++)
        count += 1;
  return count;
}

我的第一印象是 O(n log n) 但答案是 O(n)。请帮助我理解为什么它是O(n)。

Answer 1

内层循环执行n次迭代，然后是n/2，然后是n/4，等等。所以内层循环的总数迭代是:

   n + n/2 + n/4 + n/8 + ... + 1  
<= n * (1 + 1/2 + 1/4 + 1/8 + ...) 
 = 2n

(参见 Geometric series )，因此是 O(n)。