正确时间复杂度

Question

我遇到了这个问题，要求查找时间复杂度。

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

它说，它的时间复杂度O(n)，它应该是O(nlogn)作为第一个循环是logn和第二是n。

Answer 1

它说，它`时间复杂度是O（n），它应该是O（nlogn）作为 第一个循环是LOGN和第二为n。

内循环基于外循环。所以，你的要求是无效的。

而且，+ =（加法赋值运算符）的复杂度为O（1）。

对于外循环的第一次迭代，内循环将执行N次。

对于外循环的第二次迭代，内循环将执行N/2次。

而且，等等...

因此，总执行步骤

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

//登录 N次几何级数...

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

因此，代码的时间复杂度为O（N）。

所以，给出的答案是正确的。