時間複雜度分析循環：

Question

爲什麼是時間複雜度，O（n）而不是O（nlogn）？你不需要將外循環的複雜性與內循環的複雜性相乘嗎？

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; 
    } 

Answer 1

在該循環的第一次迭代的內環覆蓋n個一半。下一次迭代涵蓋四分之一，然後是八分之一，等等。您可以用下面的函數表示係數。正如你所看到的，這是一個無限的系列。因此，整個功能是O（n）