主定理
概述
主定理适用于求解形如$T(n)=aT(n/b)+f(n)$的递归式
其中$a$表示子问题个数，$n/b$表示子问题规模，$f(n)$表示分解与合并的复杂度
内容
(1)若$f(n)<n^{\log_{b} a}$，且是多项式意义上的小于，则$T(n)=O(n^{\log_{b} a})$
(2)若$f(n)=n^{\log_{b} a}$，则$T(n)=O(f(n)\lg n)$
(3)若$f(n)>n^{\log_{b} a}$，且是多项式意义上的大于，且$\forall c<1$和所有足够大的$n$有 $af(n/b)<=cf(n)$，则$T(n)=O(f(n))$
解释
以上三条中的大于或小于指的是多项式意义上的
多项式意义上的小于和大于：若$\exists \varepsilon >0$使得f(n)n^{\varepsilon}=g(n)，则称f(n)在多项式意义上小于g(n)，g(n)在多项式意义上大于f(n)
第三条中后面的限制条件称为正则条件
但是以上三条未覆盖所有的情况，不是多项式意义上的大于或小于的递归式是无法用主定理求解的
举个栗子
我们知道CDQ分治套莫队算法的递归式为$T(n)=2(T/2)+O(n\sqrt n)$
由于$a=2,b=2$,所以$g(n)=n^{\log_{a}^{b}}=n，f(n)=n\sqrt n$
由于存在$\varepsilon=0.5$使得$g(n)n^\varepsilon=f(n)$，所以$f(n)$在多项式意义上大于$g(n)$
将正则条件解出后得到$c^2>=0.5$，所以存在c使得正则条件满足
所以$T(n)=O(n\sqrt n)$
调和级数
定义
级数$S=\sum_{i=1}^{+oo} \frac{1}{i}$称为调和级数
实际上$S=ln(n+1)+r$,其中$r$被称为“欧拉常数”
证明
因为$ln(\frac{x+1}{x})=\frac{1}{x}-\frac{1}{2x^2}+\frac{1}{3x^3}-…$
所以：$\frac{1}{x}=ln(\frac{x+1}{x})+\frac{1}{2x^2}-\frac{1}{3x^3}+…$
于是将$x=1,2…$带入得到：
(1)$\frac{1}{1}=ln(2)+\frac{1}{2}-\frac{1}{3}+…$
(2)$\frac{1}{2}=ln(\frac{3}{2})+\frac{1}{2\times 4}-\frac{1}{3\times 8}+…$
…
(n)$\frac{1}{n}=ln(\frac{n+1}{n})+\frac{1}{2\times n^2}-\frac{1}{3\times n^3}+…$
将(1)~(n)相加得到$S=\sum_{i=1}^{+oo}=ln(n+1)+r$
举个栗子
调和级数在证明时间复杂度上应用广泛，有时与微积分联系起来
还是上面那个例子：CDQ分治套莫队算法，$T(n)=2T(n/2)+O(n\sqrt n)$
我们注意到递归的层数为$x$时，有$2^x$个块，每个块的大小为$\frac{n}{2^x}$，处理大小为d的块需要$O(d\sqrt d)$的时间
所以处理每一层的复杂度是$O(\frac{n^{1.5}}{2^{1.5x}})$
一共有$\log n$层，所以总的复杂度为$O(\sum_{x=1}^{\log n} \frac{n^{1.5}}{2^{1.5x}})$
把$n^{1.5}$提出来得到$O(n^{1.5}\sum_{x=1}^{\log n} 2^{-0.5})$
右边的和式不好求，我们将它近似到微积分的形式：$\sum_{x=1}^{\log n} 2^{-0.5}<=\int_{0}^{\log n}(2^{-0.5}ln2)dx$
直接展开得到 $1-\frac{1}{\sqrt n}$
因此算法复杂度为$O(n^{1.5}\times (1-n^{-0.5}))=O(n\sqrt n-n)=O(n\sqrt n)$