题目

设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。

x = 2;
while (x < n / 2)
    x = 2 * x;

错因

B

把循环变量 x 当成"每次 +1"线性递增，得到 。实际上 x = 2 * x 是指数增长——每次翻倍，从 2 到 只需要约 次迭代，不是 次。

C

误以为"嵌套循环"或"循环里有乘法"就要套 。但题面里只有一层 while，不存在内外层结构；循环里也只是赋值不是新循环。 一般出现在外层 次 + 内层 次的组合（比如归并排序），不适用此处。

D

凭感觉乱估。 通常对应"双层嵌套且每层都跑 n 次"，本题循环次数远小于 n，连 都够不到，更不可能到 。

总解析

观察循环变量 的变化：每次执行 x = 2 * x， 取值依次是 。

终止条件 x >= n / 2：

也就是循环执行 次后退出，记作 。

关键点：循环变量按指数增长 → 循环次数按对数增长（对数和指数互为反函数）。

最终答案是 A。