题目

设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是( )。

x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

错因

A

把这道题套到了"二分/折半"的模板上，看到条件里有乘法就联想成对数级别。其实判断式 决定的是循环何时终止，而每轮 x 只是 +1，并没有任何"折半"动作，所以达不到 这个量级。

C

只盯着 x = x + 1 的递增动作，就直觉认为"x 要从 0 一路加到 n"，于是判定为线性。忽略了循环条件不是 x < n 而是 ：x 还远没有爬到 n 时循环就提前退出了。

D

被条件里的 误导，把"条件里有平方"等同于"循环跑了 次"。其实平方在这里是退出阈值——平方越大越早超过 n、循环越早结束，与 的方向恰好相反。

总解析

思路：循环次数取决于"条件何时第一次不成立"。

设循环第 k+1 轮进入时 x = k，循环条件检查 。循环结束的临界条件是：

也就是说 x 从 0 增长到约 就停。每轮循环体只有一次比较和一次自增，都是 。

总执行次数约为 ，故时间复杂度为：

最终答案是 B。