级数相关

定义

有数列${a_n}$,加号连接这些数,得到级数。
$\displaystyle 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$或根本没有极限。

调和级数

级数$\displaystyle 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$的取值为:$\displaystyle \sum_{i=1}^n \frac{n}{i}=n*\sum_{i=1}^n\frac{1}{i}$

$\displaystyle \sum_{i=1}^n\frac{1}{i}$$\ln n$同阶,故算法复杂度是$O(n \log n)$.

证明复杂度

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

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

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

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

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

共有$\log n$个块,故整个算法的复杂度为:$\displaystyle O(\sum_{x=0}^{\log_2 n}\frac{n^{1.5}}{2^{0.5x}})$.
由于$n^{1.5}$$x$无关,故提取出来。整个算法复杂度为:$\displaystyle O(n^{1.5} *\sum_{x=0}^{\log_2 n} 2^{-0.5x})$.
右边的和式并不好求,我们将它近似到微积分的形式:$\displaystyle \sum_{x=0}^{\log_2 n} 2^{-0.5x} ≤ \int_0^{\log_2 n}2^{-0.5x} dx$
不妨乘上常数$\ln 2$(约等于$0.69315$)。则复杂度变成: $\displaystyle \sum_{x=0}^{\log_2 n} 2^{-0.5x} ≈ \int_0^{\log_2 n}(2^{-0.5x}*\ln 2)dx$

不妨令$f(x)=2^{-0.5x}*\ln 2$,则有$F(x)=2^{-0.5x}$.
于是$\displaystyle \left. \int_0^{\log_2 n}(2^{-0.5x}*\ln 2)dx = 2^{-0.5x}\right|_0^{\log_2 n}$
直接解开,得到$1-\frac{1}{\sqrt{n}}$.

因此我们的算法复杂度是:$\displaystyle O(n^{1.5} *(1-n^{-0.5})) = O(n^{1.5}-n) = O(n\sqrt{n})$.

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


Update on 2016.8.30:

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

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

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


Update on 2016.10.3:

此坑已补。


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close