询问下述代码片段的时间复杂度：我判断为O(n²)是否有误？

先看这段代码的逻辑：

int k = 0;
for (i = 0; k < n; i++){
    k = k + i;
}

循环的终止条件是k ≥ n，而k是累加i的结果——i从0开始，每次循环后自增1，所以k的取值是0, 0+1=1, 1+2=3, 3+3=6, 6+4=10...也就是第m次循环后（m是循环执行的次数），k的值是0+1+2+...+(m-1) = m(m-1)/2（因为i从0开始，第一次循环i=0，k变成0；第二次i=1，k变成1；第m次循环时i=m-1，k累加后是前m-1个正整数的和）。

当k ≥ n时循环停止，也就是要找到最小的m，使得m(m-1)/2 ≥ n。解这个不等式可以得到m≈√(2n)，也就是说循环执行的次数是和√n成正比的，所以时间复杂度是O(√n)，而不是你认为的O(n²)。

你之前的错误在于误解了迭代次数——并不是循环执行n次，而是当累加和达到n时，迭代次数远小于n，是根号级别的。

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