c++ - 当怀疑 n log n 时，运行时复杂度呈线性

Question

无法理解为什么此代码片段的时间复杂度为 O(n)

int main() {
  int n = 10; //n can be anything
  int sum = 0;
  float pie = 3.14;
  int var = 1;

  while (var < n){
    cout << pie << endl;
    for (int j=0; j<var; j++)
      sum+=1;
    var*=2;  
  }
  cout<<sum;
}

var 的二等分意味着 log(n)，然后有一个嵌套的内部循环，显然有 2n 使得整体复杂度为 O(n)。但我不明白为什么 2n。

Answer 1

考虑 n 是 2 的幂时的情况可能会有所帮助:n = 2^m。那么代码中的迭代次数(方便地也是它计算的次数)是

1 + 2 + ... + 2^(m-1) =
2^m-1 <
n =
O(n)