信息与计算科学导论02

\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert} 这里的递归实际上也可以理解为递推

##Karatsuba算法

计算界次为$n$的多项式乘积，$naive$做法需要计算$n^2$次

一个本科生(！！！)提出了这样的算法。考虑计算$\left(ax+b\right)\left(cx+d\right)$

展开就是$acx^2+\left(ad+bc\right)x+bd$，其中$ac$和$bd$无法避免，而$\left(ad+bc\right)=\left(a+b\right)\left(c+d\right)-ac-bd$，这样我们只需要计算$\left(ad+bc\right)$、$ac$和$bd$就可以了，这样就减少了$\frac{1}{4}$的乘法次数

再套入递归中，可以得到这样一个乘法次数的计算公式$T\left(n\right)=3T\left(\lfloor\frac{n}{2}\rfloor\right)$，注意这个不是时间复杂度，不然还要加上后面加法的n次循环(这样做只是为了方便引入递归方程的概念)

考虑怎么解这个东西。只需要不停地拆开就可以得到$T\left(n\right)=3^{\log_{2}{n} }\times T_0$，其中$T_0$是一个与n无关的常数，所以我们可以认为$T\left(n\right)=3^{\log_{2}{n} }=n^{\log_2{3} }$，等号的由来可以两边取对数

这种形式的的方程被称为递归方程(recurrence equation)，通常这类问题没有一般做法，最好的做法是guess and prove……

##解的结构

这里讨论形如$T\left(n\right)=f\left(n\right)+\sum\limits_{i=1}^{k}{a_i T\left(n-i\right)}$的方程的解的结构，当然括号内部还可以更复杂，这里只是一个简单的情形

类比线性代数，递归方程也有所谓的常系数线性齐次递归方程($f\left(n\right)=0$的时候)。方程的解同样可以表示为若干通解和特解的和的集合

通解：指令$f\left(n\right)=0$，得到的递归方程的所有解

特解：指带入原方程后满足递归方程的一个解

怎么证明呢？不妨设$T_0\left(n\right)$是一个通解，$T_1\left(n\right)$是一个特解

则$T_0\left(n\right)+T_1\left(n\right)=f\left(n\right)+\sum\limits_{i=1}^{k}{a_i\left({T_0\left(n-i\right)+T_1\left(n-i\right)}\right)}$

也满足这个递归方程，因此我们说$T_0\left(n\right)+T_1\left(n\right)$也是原方程的一个解。类似地我们可以得到特解加上任意一个通解都是原方程的解

反过来也是一样的，只需要做差就行了

##特征方程求解

对于常系数线性齐次递推，我们(教材)猜测解的形式可以是等比数列(guess)

带入看看就是$V\cdot p^n=V\sum\limits_{i=1}^{k}{a_i\cdot p^{n-i} }$，这里$V$是任意常数

这是一个一元$k$次方程，也是它的特征方程，特征方程的根带入都满足常系数线性齐次幂递归方程。为了简便讨论这里假设没有重根

由解的结构我们知道，这k个通解加起来得到的仍然是原方程的解，并且每一项的系数$V$是不一样的

怎么证明这是唯一的解呢？假设存在另一个解$S\left(n\right)$，则可以列出线性方程组。这个方程组的系数矩阵是范德蒙矩阵，于是就完了。

对于有重根的情况，解可以写成$\sum\limits_{i=1}^{k-L}\left({a_i\cdot\sum\limits_{j=1}^{L_i}{\left({n^{j-1}\cdot x_i}\right)} }\right)$

其中$L$是不同根的数量，Li是重数

证明：考虑多项式$F\left(x\right)=x^n-\sum\limits_{i=1}^k{a_i\cdot x^i}$

若$x_1$是多项式的二重根，则它是$F’\left(x\right)$的单根，即$F’\left(x\right)=nx^{n-1}-\sum\limits_{i=1}^k{a_i\cdot i\cdot x^{i-1} }$

两边同事乘上x得到$xF’\left(x\right)=nx^n-\sum\limits_{i=1}^k{a_i\cdot i\cdot x^i}$，带入$x=x_1$恰好等于0

也就是说，$n\cdot {x_1}^n$也是这个递归方程的解，解就可以写成类似$\left(1+n\right){x_1}^n$这种形式了

多重根也是类似的，这里就不推了(懒)

这种方法的难点一般在找一个特解和解特征方程。找特解需要一点智慧，而高次方程通常都很不好解……

##生成函数

这是我最喜欢的方法;-P

考虑这样一个函数$F(x)=\sum\limits_{i=0}^{\infty}{T\left(i\right)x^i}$，它包含了一个数列的所有信息，并且可以作为一个整体处理

这样的东西就是生成函数(Generating Function)，也被称为母函数/形式幂级数。在这里我们不关心它是否收敛，而只在乎它的系数，x只是一个占位符号

以斐波那契数列为例子，$F_n=F_{n-1}+F_{n-2}$且$F_0=F_1=1$就可以写成$G(x)=xG(x)+x^2G(x)+1$

化简就得到$G(x)=\frac{1}{1-x-x^2}$

看起来很炫酷，但是你这一顿操作也没有得到数列公式啊？

首先考虑一个等比数列$T(n)=p^n$，则很容易写出这个数列的生成函数$H(x)=\sum\limits_{i=0}^{\infty}{\left(px\right)^{i} }$

既然是等比数列，那么就可以写成$H(x)=\frac{1}{1-px}$，之所以略去了一项是因为我们可以令x任意取值使得这一项是无穷小

这提示我们可以把$G(x)$拆成等比数列之和，于是这个就很简单了

如果不能裂项怎么办？再考虑$P(x)=\frac{1}{\left(1-px\right)^k}$

观察第l项的系数，这里是k个等比数列相乘，这k个项的未知数上指数之和为l，p的指数之和也为l，这里用隔板法就可以做了，系数就是$\binom{l+k-1}{k-1}\cdot p^l$

这里得出的结论和上面的方法是一致的，也就是我们总能得到若干个等比数列的线性组合，它满足递归方程

有一点非常重要的是，在使用生成函数方法时，要小心处理前k项的值，如果是未知的最好设出来，不然会有漏解的情况。不过有的时候用这种方法求一个特解也是极好的，结合上面的方法就很好啦~

还有一些生成函数的运算法则，这个只需要知道两个生成函数相乘得到的是卷积就可以了，剩下的都比较简单

##算子

这个听得比较懵逼，但是dl说它足够抽象，可以带来新的视角(囧)，先随便写写回来填坑

算子可以理解为是一个对数列的操作，即$opt(T(n))$得到得还是一个数列。我们把能使一个数列变成0的算子称为消去子(annihilator)

一个想法是，如果我们找到了把$T(n)$消成0的算子g，和g能消去的所有数列的集合$P$，那么我们就可以认为是找到了所有的解(饶舌)

这个想法看上去不那么直观，甚至有点刻意的味道……

课件给出了两个最基本的算子$L$和$c$，分别表示把数列左移一位、每一项乘上常数c

习题中出现的两种算子$\triangle$和$\sum$分别表示差分和求和(可以理解为求导和积分)，类似的甚至有分步积分的形式

法则：

1. 基础的两种消去子满足交换律、结合律(显然)

2. 假如算子A消去了F，B消去了G，则AB能消去F+G

这里证明一下法则2：$AB(F+G)=ABF+ABG=B(AF)+A(BG)=0$

例子：解递归方程$T(n)=2T(\sqrt{n})+\log n$

注意到我们知道的递归方程解法都只和加减法有关，于是考虑变形。令$n=2^k$,则有$T(2^k)=2T(2^{\frac{k}{2} })+k$

记$t(k)=T(2^k)$，则有$t(k)=2t(\frac{k}{2})+k$，故技重施再令$k=2^u$，则$t(2^u)=2t(2^{u-1})+2^u$

于是$t’(u)=2t’(u-1)+2^u$

先去掉$2^u$的项观察齐次的部分$t’(u)=2t’(u-1)$，这个东西的消去子是$(L-2)$

把这个算子施加在数列上可以得到$(L-2)t’(u)=Lt’(u)-2t’(u)=t’(u+1)-2t’(u)=2^{u+1}$，这一步还是很好理解的

那么我们就得到了一个新的数列$(L-2)t’(u)=2^{u+1}$，这个东西的消去子又是$(L-2)$，于是$(L-2)^2t’(u)=0$

这个消去子能消去哪些数列呢？类比消去子和特征方程，不难发现这个东西能消去形如$(c_1+c_2n)\cdot 2^n$的数列

因此有$t’(u)=(c_1+c_2u)\cdot 2^u$，即$t(k)=(c_1+c_2\cdot\log k)\cdot k$

因此有$T(n)=\log n\cdot(c_1+c_2\cdot \log\log n)$

##渐进解

很多时候(大部分时候)我们是不能得出递归方程的精确解的，通常我们只能得到一个渐进意义下的解(但这不意味着我们不关心确解，当然越精确越好~)

渐进意义下(asymptotically)有点类似数学分析里的等价无穷大/等价无穷小

我们称函数$f(x)$的增长速度在渐进意义下不超过$g(x)$，代表$\exists N,M>0$，当$n>N$时，恒有$f(x)\le M\cdot g(x)$成立，即$\lim\limits_{n\rightarrow \infty}{\frac{f(x)}{g(x)} }< M$，其中$M$ 是个常数。

如果这里的$M$是0，我们认为$f(x)$也是不超过$g(x)$的。

上述两种情况记作$f(x)=O(g(x))$，这实际上是一个不等号，包含了渐进意义下等价和小于两种情况(M是否为0)

需要注意的是，这里我们研究的函数可以认为都是非负的、定义域在正整数上的函数。因为这里的分析来源于算法的复杂度分析，倘若一个算法的复杂度和输入规模无关(或者说消耗时间为负数，它越跑越快雾)，那么我们就没有什么必要研究这个算法了……

同时还有如下定义：

1. $f(x)=\Theta(g(x))\iff f(x)=O(g(x))$且$g(x)=O(f(x))$，这样就排除了$M=0$的情况

2. $f(x)=o(g(x))\iff g(x)=O(f(x))$

不难发现，这三种符号对应了不同的二元关系(联系2、3章)，所有的多项式(这里所说的多项式指数可以是实数，甚至可以带log等函数)都可以由一个最简单的形式代表

还有一个很有意思的结论：$\sum\limits_{i=1}^{k}{f_i(n)}\le\sum\limits_{i=1}^{k}{f_{max}(n)}=k\cdot f_{max}(n)=\Theta(f_{max}(n))$，这里$k$是和n无关的常数。这个结论写出来就证明完了

##Master Theorem

这个太强了！之前看的一直是简略版本，这里是一个更加详尽的版本

考虑形如$T\left(n\right)=aT\left(\lfloor\frac{n}{b}\rfloor\right)+f(n)$的递归方程

分三种情况：

1. 若$f(n)=\Theta\left(n^c\right)$，且$c<\log_ba$，那么$T\left(n\right)=\Theta\left(n^{\log_ba}\right)$

1. 若$f(n)=\Theta\left(n^c\right)$，且$c>\log_ba$，且$f(n)$满足正则条件(regular condition)，那么$T\left(n\right)=\Theta\left(n^c\right)$

2. 若$f(n)=\Theta\left(n^{\log_ba}\log^k n\right)$，且$k> -1$，则$T\left(n\right)=\Theta\left(n^{\log_ba}\log^{k+1}n\right)$

正则条件指的是对于函数$f(n)$，$\exists d< 1$，当n充分大时，满足$a\cdot f\left(\frac{n}{b}\right)< d\cdot f\left(n\right)$

注意到这里给出的都是$\Theta$，这可比网上一搜一大堆的$O$强多了

一个通俗的理解是，考虑等号右边两项哪个更大，则主要的复杂度取决于哪个。如果要证明可以把递归拆开然后用等比数列求和的公式，讨论公比就可以得到这个结论了。实在不行归纳也可以证明

有的时候不能用注定理，比如说$f(n)=n^{1-\frac{1}{n} }$，这里不存在任何一个$c=1-\frac{1}{n}$