一些求和式的估算 & 杜教筛时间复杂度证明

本文内容概要：

\(A=\sum\limits_{i=1}^n\dfrac1{\sqrt i}=1+\dfrac1{\sqrt2}+\cdots+\dfrac1{\sqrt n}\)
\(O(\sqrt n)\) ，将给出一种只需使用初中数学知识的放缩
\(B=\sum\limits_{i=1}^n\sqrt i=1+\sqrt2+\cdots+\sqrt n\)
\(O(n\sqrt n)\) ，使用积分进行放缩
\(C=\sum\limits_{i=1}^n\dfrac1i=1+\dfrac12+\cdots+\dfrac1n\)
著名的调和级数，\(O(\ln n)\) ，主要介绍一种证明下界的方法
杜教筛时间复杂度证明
不再讲解算法，阅读前请确保你已经事先了解杜教筛

一些证明来自于我的数学老师，在此表示感谢

\(A=\sum\limits_{i=1}^n\dfrac1{\sqrt i}\)

考虑放缩： \(\dfrac1{\sqrt i+\sqrt{i+1}}<\dfrac1{2\sqrt i}<\dfrac1{\sqrt{i-1}+\sqrt i}\)

两边裂个项：\(\sqrt{i+1}-\sqrt i<\dfrac1{2\sqrt i}<\sqrt i-\sqrt{i-1}\)

求和：\(\sum\limits_{i=1}^n\sqrt{i+1}-\sqrt i<\sum\limits_{i=1}^n\dfrac1{2\sqrt i}<\sum\limits_{i=1}^n\sqrt i-\sqrt{i-1}\)

即 \(\sqrt{n+1}-1<\dfrac12A<\sqrt n\)

故 \(2\sqrt{n+1}-2<A<2\sqrt n\)

注意到

\[\int_0^n\sqrt x\cdot dx<\sum_{x=1}^n\sqrt x<\int_0^n\sqrt{x+1}\cdot dx \]

放个图，应该能帮助理解

直接积出来，得到 \(\dfrac23n^{1.5}<B<\dfrac23\left[(n+1)^{1.5}-1\right]\)

这种处理技巧对应的专有名词是积分判别法

类似地，用积分容易证明 \(\ln(1+n)<C<1+\ln n\) ，这里不再赘述，读者可自行完成
（严格地说，\(n=1\) 时是能取到上界的，但问题不大）

下面给出另一种 \(C>\ln(n+1)\) 的证明方法

考虑一个结论： \(x-1\ge\ln x\) （当且仅当 \(x=1\) 时取等）
似乎是高中数学常见结论？不证了

令 \(x=2,\dfrac32,\dfrac43,\cdots,\dfrac{n+1}n\) ，代入并求和：

\[\sum_{i=1}^n\left(\dfrac{i+1}i-1\right)>\sum_{i=1}^n\ln\dfrac{i+1}i \]

\[\sum_{i=1}^n\dfrac1i>\ln\left(\prod_{i=1}^n\dfrac{i+1}i\right) \]

\[C>\ln(n+1) \]

证毕

如需了解更多请自行百度调和级数

不妨考虑最简单的情形： \(S(n)=\sum\limits_{i=2}^nS\left(\left\lfloor\dfrac ni\right\rfloor\right)\) ，使用整除分块递归求解

注意，时间复杂度写成 \(T(n)=O(\sqrt n)+\sum\limits_{i=2}^{\sqrt n}(T(i)+T(\frac ni))\) 的证明都是错的。
\(T(200000)\) 已经超过 1e8 了。自行体会。

证明应当考虑到杜教筛是有记忆化的
于是整个算法中，每个 \(S(n/i)(i\in\mathbb N)\) 都恰被计算了一次

于是时间复杂度为 \(O(~\sum\limits_{j=n/i}\!\sqrt j~)\)

\(j\le \sqrt n\) 的部分显然可以忽略，考虑剩下的

\[\sum_{i=1}^{\sqrt n}\sqrt{\dfrac ni}=\sqrt n\sum_{i=1}^{\sqrt n}\dfrac1{\sqrt i}\approx \sqrt n\cdot2\sqrt{\sqrt n}=2n^{3/4} \]

于是时间复杂度就是 \(O(n^{3/4})\)

我们还可以优化，用线性筛预处理 \(S(1)\sim S(k) (k\ge \sqrt n)\)

这样就可以忽略 \(j\le k\) 的部分

\[\sum_{i=1}^{n/k}\sqrt{\dfrac ni}\approx \dfrac{2n}{\sqrt k} \]

时间复杂度就是 \(O\left(k+\dfrac n{\sqrt k}\right)\) ，当 \(k\) 为 \(O(n^{2/3})\) 级别时取到最优 \(O(n^{2/3})\) 。