Big-O：これらのループの時間が複雑であるのはなぜですか。

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)だと思いました（すなわち、我々が到達する内部ループを削除した場合）

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

.

これはO(N LogN)ですか？そして、内側のループは直線的に増加するだけのO(Log N)になることがわかります。だから私はそれがO(N)であることになっていると思います。私の考えに何がうまくいくのでしょうか？

Answer 1

内部ループが撮っている一歩の数を見てください。 $ n +¥frac {1} {2} n +¥frac {1} {4} n +¥cdots $ 。ただし、 Geometric Series を伝えます：

$$ \ sum_ {k= 0} ^ {\ lceil \ log n \ rceil + c} \ frac {n} {2 ^ k}