正確時間複雜度

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）。

所以，給出的答案是正確的。