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

A. $O(\log n)$ B. $O(n)$ C. $O(\sqrt{n})$ D. $O(n^2)$

复杂度分析

[tag_link]

正确答案：A

程序首先将变量 $i$ 初始化为 $n$ 的平方，即 $i=n^2$ 。

然后进入 while 循环，循环条件为 $i\ne 1$ ，每次迭代将 $i$ 除以 $2$ 。 循环的迭代次数取决于 $i$ 从 $n^2$ 减少到 $1$ 所需除以 $2$ 的次数。

设迭代次数为

$k$ ，经过 $k$ 次迭代后， $i$ 的值变为 $n^2/2^k$ 。

当循环终止时， $i=1$ ，因此有 $n^2/2^k=1$ ，即 $n^2=2^k$ 。 取对数可得 $k={\log }_2(n^2)=2{\log }_{2}n$ 。

在时间复杂度分析中，常数因子可以忽略，因此迭代次数

$k$ 的数量级为 $O(\log n)$ 。

所以，该程序片段的时间复杂度是 $O(\log n)$ 。 对比选项，A 正确。