定义法 $O(n)$
记
$$
k = \lfloor log_2n \rfloor
$$
则
$$
\begin{aligned}
log_2n - 1 < k \le log_2n
\end{aligned}
$$
则
$$
\begin{aligned}
2^k \le n < 2^{k + 1}\\
\end{aligned}
$$
由于 $log_2n$ 和 $\lfloor x \rfloor$ 都是单调增函数,则 $\lfloor log_2n \rfloor$ 也是,可用双指针优化。
for (int i = 2, j = 1; i <= n; i++) {
while (1 << j + 1 <= i) j++;
lg2[i] = j;
}
上述代码中,内层 while
总共执行 $log_2n$ 次,可忽略不计。
递推法 $O(n)$
由
$$
\begin{aligned}
log_2n &= log_2(\frac{n}{2} \times 2) \\
&= log_2 \frac{n}{2} + log_22 \\
&= log_2 \frac{n}{2} + 1
\end{aligned}
$$
得
$$
\begin{eqnarray}
\lfloor log_2n \rfloor &= \lfloor log_2 \frac{n}{2} + 1 \rfloor \\
&= \lfloor log_2 \frac{n}{2} \rfloor + 1 \\
&= \lfloor log_2 \lfloor \frac{n}{2} \rfloor \rfloor + 1 \tag{1}
\end{eqnarray}
$$
关于式 $(1)$,若 $n$ 为偶数显然成立。若 $n$ 为奇数
设
$$
n = 2k + 1, k \in \mathbb{N^{+}}
$$
则
$$
\begin{aligned}
& \frac{n}{2} = k + \frac{1}{2} \\
& \lfloor \frac{n}{2} \rfloor = k
\end{aligned}
$$
设
$$
2^m \le k < 2^{m + 1}, m \in \mathbb{N}
$$
则
$$
2^m \le k + \frac{1}{2} < 2^{m + 1}
$$
则
$$
\lfloor log_2k \rfloor = \lfloor log_2(k + \frac{1}{2}) \rfloor = m
$$
则
$$
\lfloor log_2\lfloor \frac{n}{2} \rfloor \rfloor = \lfloor log_2\frac{n}{2} \rfloor
$$
for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;