note[5]
例：化简该复杂度 \[ \sum_{k=1}^{\pi(n)} \frac{1}{p_k} \] 其中 \(\pi(n)\) 为素数计数函数，\(p_k\) 表示第 \(k\) 大的素数。
解：
引理：有以下等式 link \[ \int \frac{\mathrm{d}x}{x \ln x} = \ln(\ln x) \] 证明：
根据换元法公式：令 \(u=g(x)\) ，则 \(du = g^{\prime}(x)dx\) 。
令 \(u = \ln x\) ，则 \(\mathrm{d}u = \frac{1}{x}\mathrm{d}x\) \[ \int \frac{1}{x \ln x} \mathrm{d}x = \int \frac{1}{u} \mathrm{d}u = \ln u \] 故 \[ \int \frac{\mathrm{d}x}{x \ln x} = \ln (\ln x)\qquad \] 证毕。 \(\square\)
根据素数定理有 \(\pi(n) = \Theta\left(\frac{n}{\ln n}\right)\) ，可知第 \(n\) 个素数的大小为 \(\Theta\left(n\ln n\right)\)
则有 \[ \begin{aligned} \sum_{k=1}^{\pi(n)} \frac{1}{p_k} &= \mathcal{O}\left(\sum_{k=2}^{\pi(n)} \frac{1}{k \ln k}\right) \\&=\mathcal{O}\left(\int_2^{\pi(n)} \frac{\mathrm{d}x}{x \ln x}\right) \end{aligned} \] 根据引理可得 \[ \mathcal{O}\left(\int_2^{\pi(n)} \frac{\mathrm{d}x}{x \ln x}\right) = \mathcal{O}\left(\ln \ln \pi(n)\right) = \mathcal{O}\left(\log \log n\right) \]
参考文献
