408 每日一题 Day4#

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

1
x = 1.0;
2
while (x < n)
3
  x += 0.01 * x

A. $O(1)$
B. $O(\log_{2} n)$
C. $O(n)$
D. $O(n\log_{2} n)$

正确答案：B#

解析：
$x += 0.01 * x$ 等价于 $x *= 1.01$
设循环执行 $k$ 次，则有 $x=1.01^k$，循环条件 $1.01^k \ge n$，解得 $k=\log_{1.01}n=\frac{\log_2 n}{\log_2 1.01}$，由于 $\log_2 1.01$ 为常数，因此时间复杂度为 $O(\log_{2} n)$。