正確な時間複雑さ

Question

時間の複雑さを見つけることを求めるこの質問に出会った。

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

これは、最初のループがlognであり、第二はnあるとして、時間の複雑さは、それがO(nlogn)する必要があり、O(n)さだと言います。

Answer 1

なお、第1のループがLOGNおよび第2 Nである としては、O（nlogn）であるべきで、それは `sの時間複雑度はO（N）であることを述べています。

内側ループは外側ループに基づいています。したがって、あなたの主張は有効ではありません。

そして、+ =（加算代入演算子）の複雑さはO（1）です。

外部ループの最初の反復では、内部ループがN回実行されます。

外部ループの2番目の反復では、内部ループはN/2回実行されます。

そして、ように...

したがって、合計実行は N回等比数列を記録//

 = N + N/2 + ... + 1 

ステップ...したがって

 ~ N/(1-(1/2)) (Infinite GP Summation Formula) //though the series would go up to 1 
     ~ 2N. 
     // ~ means approximately. 

、コードの時間複雑度はO（N）となる。

これは正しい答えです。