关于一段C++函数时间复杂度的疑问：是O(n²)还是O(1)？

你的判断完全正确，这个函数的时间复杂度是O(1)，而非O(n²)，具体分析如下：

先看代码逻辑：

void foo(int n){
  n=n*n;
  for (int i=0;i<n;i++){
    if(n<10)
      cout << i;
    else
      break;
  }
}

1. 函数首先将输入的n平方，但后续循环的执行逻辑完全由平方后的n是否小于10决定：

   • 若平方后的n≥10，循环第一次判断时就会触发else分支直接break，循环体一次都不执行；
   • 若平方后的n<10，说明原输入n只能是1、2、3（因为3²=9<10，4²=16≥10），此时循环最多执行9次（当原n=3时，平方后n=9，循环i从0到8，共9次）。

2. 时间复杂度的核心是看随着输入规模增大，执行次数的增长趋势：这里不管输入的n多大，循环的执行次数最多是固定的9次，属于常数级别的执行量，不会随n的增大而增长，因此时间复杂度是O(1)。而O(n²)是指执行次数会随输入规模的平方级增长，显然这个函数完全不符合这个特征。

内容的提问来源于stack exchange，提问作者Muhammad Taha Ali