与えられた関数の時間複雑さを求める

Question

与えられたプログラムに対して、時間の複雑さは何か。私の理解へ

int count = 0; 

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

iループを分割し、征服し、それゆえO(logn)あるとjループがO(n)あるので、それはO(nlogn)する必要があります。

ただし、正解はO(n)です。なぜ誰かが説明できますか？

Answer 1

それはO(n)です：

外側のループはO(logn)反復を持って、iはnから始まり、各反復上半分ますので、。

今度は、内側のループの繰り返し回数を考える：外側のループの最初の繰り返しで

• 、内側のループは（i==n以降）n反復を持っています。

• 外側ループの2番目の反復では、内側ループはn/2回の反復（i==n/2以降）です。 log(n)「番目（最終的な）外側ループの反復において

...

• 、内側ループは（i==1以降）1回の反復を有します。

  我々が得るすべての内側ループの反復を合計

：内部ループのための

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