为何嵌套循环代码的时间复杂度为O(n)而非疑似的O(n log 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;
}

核心推导逻辑 #

• 外层while循环中，var初始值为1，每次循环结束后倍增，直到var >= n时停止，因此var的取值序列为 1、2、4、8...2^m，其中2^m是小于n的最大2的整数次幂，外层循环总执行次数为log₂n次。
• 内层for循环的执行次数等于当前var的值，因此所有内层循环的总执行次数为等比数列求和：

  S = 1 + 2 + 4 + 8 + ... + 2^m
  根据等比数列求和公式可得：S = 2^(m+1) - 1

• 结合var的终止条件可得：2^m < n ≤ 2^(m+1)，不等式两边乘2得2^(m+1) < 2n，代入求和公式可得S < 2n -1，即内层循环总操作数永远小于2n，这就是“总操作数约为2n”的来源。

复杂度结论 #

外层循环中除内层for外的其他操作（打印pie、更新var）总次数仅为log₂n，和线性量级的2n相比可以忽略，因此整体时间复杂度为O(n)。

可通过实际示例验证：n=10时，var的取值为1、2、4、8，内层总执行次数为1+2+4+8=15，确实小于2*10=20，符合推导结论。

内容的提问来源于stack exchange，提问作者CD86