第 1 题：设 n是描述问题规模的非负整数，下面程序片段的时间复杂度是 。x=2; while(x A. O(log 2 n)B. O(n)C. O(nlog 2 n)D. O(n 2 )

考查要点：本题主要考查对循环时间复杂度的分析能力，需要理解循环变量的增长规律，并将其转化为数学表达式进行求解。

解题核心思路：

1. 观察循环变量的变化：循环中x的值每次乘以2，呈现指数增长。
2. 确定循环终止条件：当x >= n/2时循环停止。
3. 建立数学关系：通过x的初始值和增长规律，推导出循环次数与n的关系，最终得出时间复杂度。

破题关键点：

• 指数增长的对数性质：x每次翻倍，循环次数与log n相关。
• 对数底数的无关性：虽然题目选项中明确给出底数为2，但时间复杂度中对数的底数不影响渐进阶。

循环变量分析

初始时x = 2，每次循环x变为原来的2倍，即x = 2, 4, 8, 16, ...。循环终止条件为x >= n/2。

循环次数推导

设循环执行了k次，则第k次循环后x = 2^{k+1}。循环终止的条件为：
$2^{k+1} \geq \frac{n}{2}$
取以2为底的对数：
$k+1 \geq \log_2 \left( \frac{n}{2} \right) = \log_2 n - 1$
解得：
$k \geq \log_2 n - 2$
因此，循环次数k约为O(\log_2 n)。

时间复杂度结论

循环体内的操作为常数时间，总时间复杂度为循环次数的函数，即O(\log_2 n)。