这里的递归实际上也可以理解为递推
##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\)分别表示差分和求和(可以理解为求导和积分)，类似的甚至有分步积分的形式
法则：
基础的两种消去子满足交换律、结合律(显然)
假如算子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)
需要注意的是，这里我们研究的函数可以认为都是非负的、定义域在正整数上的函数。因为这里的分析来源于算法的复杂度分析，倘若一个算法的复杂度和输入规模无关(或者说消耗时间为负数，它越跑越快雾)，那么我们就没有什么必要研究这个算法了……
同时还有如下定义：
\(f(x)=\Theta(g(x))\iff f(x)=O(g(x))\)且\(g(x)=O(f(x))\)，这样就排除了\(M=0\)的情况
\(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)\)的递归方程
分三种情况：
若\(f(n)=\Theta\left(n^c\right)\)，且\(c<\log_ba\)，那么\(T\left(n\right)=\Theta\left(n^{\log_ba}\right)\)
若\(f(n)=\Theta\left(n^c\right)\)，且\(c>\log_ba\)，且\(f(n)\)满足正则条件(regular condition)，那么\(T\left(n\right)=\Theta\left(n^c\right)\)
若\(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}\)