识别给定while循环的时间复杂度：是否为O(n)或O(n²)

你提供的这段代码时间复杂度不满足O(n)，确实属于O(n²)量级，远高于你预期的线性时间复杂度。

具体推导过程 #

你给出的代码如下：

int a = 0;
int b = a + 1;
while (a < n) {
    b++;
    if (b == n) {
        a++;
        b = a + 1;
    }
}

我们逐次统计循环执行次数：

• a = 0时，b从1自增到n，循环共执行 n-1 次
• a = 1时，b从2自增到n，循环共执行 n-2 次
• ...
• a = k时，b从k+1自增到n，循环共执行 n-k-1 次
• ...
• a = n-2时，b从n-1自增到n，循环共执行 1 次
• a = n-1时，a < n 条件不满足，循环终止

总循环次数为等差数列求和：

(n-1) + (n-2) + ... + 1 = n(n-1)/2

忽略低阶项和常数系数后，时间复杂度最终为 O(n²)。

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