大O：为什么这些循环的时间复杂度是 O(N)？

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) 时间复杂度。我以为是 O(N LogN)（IE。如果我们删除内循环，我们会得到）

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

这是 O(Log N) 不是吗？内循环结果是 O(N) 因为它只是线性增加。所以我认为应该是 O(Log N * N). 。我的想法可能出了什么问题？

Answer 1

查看内循环执行了多少步。它是 $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$. 。但是，那 几何系列 告诉我们：

$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^k} = 2n$$