题目

下列函数的时间复杂度是（ ）。

int func(int n) {
    int i = 0, sum = 0;
    while(sum < n)
        sum += ++i;
    return i;
}

错因

A

把循环模式当成"二分类"——只要有循环就先想到 。但 的本质是每次问题规模减半（如二分查找 low/high 折中），这里 sum 是累加 ++i，没有任何"减半"或"翻倍"的成分，套不上 。

C

只看到"i 每次加 1"就直接联想到 ，忘了真正决定循环次数的是终止条件 sum < n。sum 增长比 i 快得多（sum 是前 项和，二次增长），因此 i 远早于 n 就让循环停掉，实际循环次数是 量级而不是 。

D

把"线性 对数"凑出来——既看到循环又看到累加，于是猜个 。这是排序题里最常见的复杂度，但本题没有递归/分治结构，凑不出 因子。

总解析

关键：盯紧循环终止条件，因为它决定了循环执行多少次。

设循环执行 次后退出。每轮 i 自增 1 再累加进 sum：

循环退出条件是 sum >= n，即：

去掉常数因子，循环执行次数为 。

最终答案是 B。

小结：判断循环复杂度时不要数循环变量增长方式，要看累加量逼近 n 的速度——这里 sum 以二次速度增长，所以 i 只需 量级就够。