定义法 $O(n)$
记
$$ k = \lfloor log_2n \rfloor $$
即
$$ \begin{aligned} k \le log_2n < k + 1 \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;