级数相关

定义

有数列$a_n$，加号连接这些数，得到级数。
$S=\sum _{i=1}^{\infty }{a}_i$

如果$S$拥有极限，则称级数$S$收敛。否则称级数$S$发散。

条件收敛：如果$S=\sum a_i$收敛而$\sum |a_i|$发散，则称$S$条件收敛。

重要性质：对发散级数不能更改求和顺序。（加括号属于更改求和顺序）

黎曼级数定理

一个颠覆常规观念的结论：
如果级数$S$条件收敛，那么我们可以指定任意实数$M$，通过调整级数的求和顺序，使得$S=M$；也可以通过调整级数的求和顺序，使得$S=\infty$,$S=-\infty$或根本没有极限。

调和级数

级数$S=\sum _{i=1}^{\infty }\frac{1}{i}$ 称为“调和级数”。

它的前$n$项和$S_n=\ln (n+1)+r$,其中$r$被称为“欧拉常数”。

近年来出现了声称调和级数收敛的狗屁论调，我们容易证明调和级数发散：

$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}\cdots >1+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\cdots$
又有右边柿子等于$1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}\cdots$，发散。
故调和级数发散。

调和级数与$\ln n$同阶，故经常用来证明复杂度。例如下面的代码：

for(i=1;i<=n;i++)
    for(j=1;i*j<=n;j++)
        //do something excited in O(1)

考虑对于某个$i$，$j$将会有$\frac{n}{i}$个取值。
那么总的$j$的取值为：$\sum _{i=1}^n\frac{n}{i}=n\ast \sum _{i=1}^n\frac{1}{i}$。

而$\sum _{i=1}^n\frac{1}{i}$与$\ln n$同阶，故算法复杂度是$O\left(n\log n\right)$.

证明复杂度

有时与微积分联系起来，证明复杂度。

例如一个典型的例子。在CDQ分治套莫队算法的时候，会有这种复杂度：$T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n\sqrt{n}\right)$.
惯用伎俩，把复杂度按层考虑。

如上图。对于每个大小为$d$的块，需要耗费$O\left(d\sqrt{d}\right)$的复杂度来处理。

那么以“第几层”为自变量$x$，则有：第$x$层有$2^x$个块，每块大小为$\frac{n}{2^x}$；故处理每块的复杂度是$O\left(\frac{n}{2^x}\sqrt{\frac{n}{2^x}}\right)$.化简为$O\left(\frac{n^{1.5}}{2^{1.5x}}\right)$.

由于这层有$2^x$个块，则处理整层的复杂度是$O\left(\frac{n^{1.5}}{2^{0.5x}}\right)$.

共有$\log n$个块，故整个算法的复杂度为：$O\left(\sum _{x=0}^{{\log }_{2}n}\frac{n^{1.5}}{2^{0.5x}}\right)$.
由于$n^{1.5}$与$x$无关，故提取出来。整个算法复杂度为：$O(n^{1.5}\ast \sum _{x=0}^{{\log }_{2}n}{2}^{-0.5x})$.
右边的和式并不好求，我们将它近似到微积分的形式：$\sum _{x=0}^{{\log }_{2}n}{2}^{-0.5x}\le {\int }_0^{{\log }_{2}n}{2}^{-0.5x}dx$
不妨乘上常数$\ln 2$（约等于$0.69315$）。则复杂度变成： $\sum _{x=0}^{{\log }_{2}n}{2}^{-0.5x}\approx {\int }_0^{{\log }_{2}n}(2^{-0.5x}\ast \ln 2)dx$

不妨令$f\left(x\right)=2^{-0.5x}\ast \ln 2$，则有$F\left(x\right)=2^{-0.5x}$.
于是${{\int }_0^{{\log }_{2}n}(2^{-0.5x}\ast \ln 2)dx=2^{-0.5x}|}_0^{{\log }_{2}n}$
直接解开，得到$1-\frac{1}{\sqrt{n}}$.

因此我们的算法复杂度是：$O(n^{1.5}\ast (1-n^{-0.5}\left)\right)=O(n^{1.5}-n)=O\left(n\sqrt{n}\right)$.

好神奇啊，连个$\log$都不带。

---

Update on 2016.8.30:

uoj的人给出了一种很劲的方法：可以用“主定理”求出上面的递归式的复杂度.

$T\left(n\right)=2T\left(\frac{n}{2}\right)+O\left(n^{1.5}\right)$.
因为$2<2^{1.5}$，故有$T\left(n\right)=O\left(n^{1.5}\right)=O\left(n\sqrt{n}\right)$.(主定理第二条)

这就完了……去看看算法导论，留坑待补。

---

Update on 2016.10.3:

此坑已补。