数学复健4-递归
一个只写了有限行的规则，究竟能定义哪些函数，又能完成哪些计算？
如何生成结果？为什么生成过程合法？
递归
递归的概念比较类似归纳法，不过归纳法是一种证明方法，而递归是一种定义对象的方法，由初值和递归关系组成
给定初值 $a_0$，以及一个构造规则 $G$，定义序列：
$$ a_0=c$$
$$ a_{n+1}=G(n,a_n)$$
这叫作一个递归定义。
例如：
$$ a_0=1, \qquad a_{n+1}=2a_n.$$
于是：
$$ a_n=2^n.$$
递归定义必须说明：
- 初始对象是什么；
- 下一步如何构造；
- 每一步是否仍落在允许的对象世界中。
Fibonacci 数列
最经典的递归示例（兔子繁殖问题），斐波那契数列：
$$ F_0=0, \qquad F_1=1,$$
以及：
$$ F_{n+2}=F_{n+1}+F_n$$
前几项为：
$$ 0,1,1,2,3,5,8,13,\ldots.$$
阶乘
阶乘可以递归定义：
$$ 0!=1,$$
$$ (n+1)!=(n+1)n!.$$
这给出：
$$ 1!=1,\quad 2!=2,\quad 3!=6,\quad 4!=24.$$
二叉树
一个二叉树可以由下面的构造规则定义：
- 空对象 $\varnothing$ 是一棵二叉树；
- 如果 $L$ 和 $R$ 已经是二叉树，$x$ 是保存在节点中的一个数据值，那么 $\operatorname{node}(L,x,R)$ 也是一棵二叉树。
在第二条规则中，$x$ 所在的位置叫作根节点，$L$ 和 $R$ 分别叫作左子树和右子树。
树的节点数：
$$ \operatorname{size}(\varnothing)=0,$$
$$ \operatorname{size}(\operatorname{node}(L,x,R)) = 1+\operatorname{size}(L)+\operatorname{size}(R).$$
递推关系
定义
一个数列：
$$ (a_n)_{n\geq0}$$
若满足：
$$ a_{n+k} = G(a_{n+k-1},\ldots,a_n,n),$$
就称它满足一个递推关系。
递推关系规定：
只要知道较早项，就能构造较晚项。
如果 $a_{n+k}$ 由前面的 $k$ 项决定，就说递推的阶数为 $k$。
若递推可以写成：
$$ a_{n+k} = c_{k-1}a_{n+k-1} +\cdots+ c_0a_n$$
其中系数 $c_0,\ldots,c_{k-1}$ 不依赖各项 $a_j$，就叫作 $k$ 阶线性递推。
右侧没有额外的外部项时，称为齐次。
外部项：与 $n$ 有关，但不含 $a$ 的项，如下面的 $f(n)$
$$ a_{n+k} = c_{k-1}a_{n+k-1} +\cdots+ c_0a_n + f(n)$$
一阶线性递推
最简单的形式是：
$$ a_{n+1}=ra_n+b.$$
其中 $r,b$ 是常数。
不动点
一个数 $a_\ast$ 如果经过更新后保持不变，即：
$$ a_\ast=ra_\ast+b,$$
就叫作这个更新规则的不动点。
如果 $r\neq1$，不动点为：
$$ a_\ast=\frac{b}{1-r}.$$
令：
$$ c_n=a_n-a_\ast,$$
则：
$$ c_{n+1}=rc_n.$$
因此：
$$ c_n=r^nc_0,$$
从而：
$$ a_n=a_\ast+r^n(a_0-a_\ast)$$
差分
对数列 $(a_n)$，相邻两项之差：
$$ \Delta a_n=a_{n+1}-a_n$$
叫作它的一阶差分。
差分描述离散步骤之间的变化
二阶齐次线性递推
当前项与之前两项相关、且不含外部项的递推就是二阶齐次线性递推
特征方程
考虑：
$$ a_{n+2}=c_1a_{n+1}+c_2a_n.$$
递推的通解可以有多种表达式，对于二阶齐次线性递推，它的解空间是二维线性空间，我们只需要找到任意两个线性无关的基解，就能组合出一个通解。
我们这里尝试用指数形式求解，令：
$$ a_n=\lambda^n.$$
代入：
$$ \lambda^{n+2} = c_1\lambda^{n+1}+c_2\lambda^n.$$
若 $\lambda\neq0$，除以 $\lambda^n$：
$$ \lambda^2-c_1\lambda-c_2=0.$$
这个方程叫作特征方程。
它的根 $\lambda$ 叫作这个递推的特征根。
若有两个不同的特征根 $\lambda_1,\lambda_2$，则通解形如：
$$ a_n=A\lambda_1^n+B\lambda_2^n.$$
常数 $A,B$ 由初值决定。
Fibonacci 的显式公式
斐波那契数列就是一个二阶齐次线性递推
Fibonacci 递推：
$$ F_{n+2}=F_{n+1}+F_n$$
将 $F_n=\lambda^n$ 带入，得到特征方程：
$$ \lambda^2-\lambda-1=0.$$
两个根为：
$$ \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.$$
因此：
$$ F_n=A\varphi^n + B \psi^n$$
我们将 $F_0=0,F_1=1$带入，求解出 $A,B$ 的值
$$ A=\frac{1}{\sqrt5},\qquad B=-\frac{1}{\sqrt5}$$
将$A,B$ 代回通解
$$ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}$$
非齐次递推
若：
$$ a_{n+2}=c_1a_{n+1}+c_2a_n+h_n,$$
则称为非齐次递推。
通常分两部分：
$$ a_n = a_n^{\mathrm{hom}} + a_n^{\mathrm{part}},$$
其中：
- $a_n^{\mathrm{hom}}$ 解对应齐次方程；
- $a_n^{\mathrm{part}}$ 是非齐次项造成的一个特解。
循环不变量
定义
一个关于状态的命题 $I(s)$，如果满足：
- 初始状态满足：
$$ I(s_0);$$
- 若某次循环开始时满足 $I(s_k)$，执行循环体后仍满足：
$$ I(s_{k+1});$$
则称 $I$ 是这个循环的不变量。
本质就是归纳法：
$$ I(s_0) \quad+\quad I(s_k)\Longrightarrow I(s_{k+1}).$$
递归树
分治算法
一个问题若可以拆成若干个更小的问题，分别解决后再合并，称为分治。
例如，一个规模为 $n$ 的算法可能满足：
$$ T(n)=2T\left(\frac n2\right)+n.$$
这里：
- $T(n)$ 是输入规模为 $n$ 时的运行时间；
- $2T(n/2)$ 表示两个规模约为 $n/2$ 的子问题；
- $n$ 表示拆分和合并的额外成本。
递归树
把 $T(n)$ 展开：
把最初的问题放在第 $0$ 层，每拆分一次就进入下一层。
递归树中编号最大的非空层，叫作这棵递归树的高度。
第一层成本：
$$ n.$$
第二层有两个子问题，每个成本 $n/2$，总成本：
$$ 2\cdot\frac n2=n.$$
第三层：
$$ 4\cdot\frac n4=n.$$
每一层总成本都是 $n$。
对正数 $n$，以 $2$ 为底的对数 $\log_2 n$ 是满足：
$$ 2^k=n$$
的指数 $k$。当 $n$ 是 $2$ 的整数次幂时，它正好记录把 $n$ 反复减半多少次才会到达 $1$。
树的高度约为：
$$ \log_2n.$$
所以：
$$ \exists C>0,\ \exists n_0,\quad\forall n\geq n_0,\quad T(n)\leq Cn\log n.$$
递归树把一个大问题展开成多层小问题。每层总成本若近似相同，而层数是 $\log n$，总成本通常不超过 $n\log n$ 的某个常数倍。
渐近记号
在上文递归树中，我们提到了一个“总成本通常不超过 $n\log n$ 的某个常数倍”的概念，这就是某种渐进记号
算法运行时间除了算法的结构，还依赖机器本身、输入分布等。为了比较算法的结构的优劣，我们通常关注输入规模 $n$ 增大时的增长阶。
渐近上界
大 $O$
若存在常数 $C>0$ 和 $n_0$，使：
$$ \forall n\geq n_0,\quad 0\leq f(n)\leq Cg(n),$$
则称：
$$ f(n)=O(g(n))$$
它表示 $f$ 的增长最终不超过 $g$ 的常数倍。
渐近下界
大 $\Omega$
若存在常数 $c>0$ 和 $n_0$，使：
$$ \forall n\geq n_0,\quad 0\leq cg(n)\leq f(n),$$
则称：
$$ f(n)=\Omega(g(n))$$
它表示 $f$ 的增长最终至少达到 $g$ 的常数倍。
同阶增长
大 $\Theta$
若同时有：
$$ f(n)=O(g(n)),$$
以及：
$$ f(n)=\Omega(g(n)),$$
则称：
$$ f(n)=\Theta(g(n))$$
它表示二者具有相同的渐近增长阶。
常见增长顺序
对足够大的 $n$，常见增长率大致为：
$$ 1 \ll \log n \ll n \ll n\log n \ll n^2 \ll 2^n \ll n!.$$
渐近记号不等于精确运行时间
$$ T(n)=O(n\log n)$$
只给出充分大输入下的增长上界，不直接说明：
- 隐藏的常数；
- 小输入上的行为；
- 实际内存用量；
- 缓存与并行硬件的影响；
- 讨论的是最坏、平均还是摊还情形。
给定输入规模 $n$：
- 最坏复杂度是在所有规模为 $n$ 的输入中取最大成本；
- 平均复杂度先规定各类输入出现的权重，再对成本作加权平均；
- 摊还复杂度考察一串操作的总成本，再除以操作次数。
所以复杂度是比较算法结构的语言，不是一台具体机器的秒表。
动态规划
动态规划是一类利用递推关系求解问题的方法：它把大问题拆成重复出现的子问题，保存已经得到的子问题答案，并用这些答案构造更大问题的答案。
- 重叠子问题：不同的大问题，会反复用到同一个小问题的结果
- 最优子结构：原问题的最优解，可以由子问题的最优解组合出来
通常有两种实现方式：
- 自顶向下（记忆化递归）：递归 + 缓存答案
- 自底向上（递推，最常用）：从小的子问题开始，一步步算到大问题
最优子结构
在一组允许方案中寻找代价最小或收益最大的方案，叫作一个优化问题。
令：
- $s$ 表示当前状态；
- $A(s)$ 表示状态 $s$ 下允许选择的动作集合；
- $a\in A(s)$ 表示一个动作；
- $c(s,a)$ 表示执行动作的当前代价；
- $T(s,a)$ 表示执行后到达的下一状态；
- $V(s)$ 表示从状态 $s$ 出发能够达到的最小总代价。
如果它能写成：
$$ V(s) = \min_{a\in A(s)} \left[ c(s,a)+V(T(s,a)) \right],$$
就可能使用动态规划。
例子：爬楼梯
楼梯一共 n 阶，每次可以爬 1 阶或者 2 阶。问一共有多少种爬到楼顶的方案？
第一步：定义状态
$dp[i]$ = 爬到第 $i$ 阶楼梯的方案数
第二步：构造转移方程，当前的最优解可以用先前的最优解组合出来
想要到达第 $i$ 阶，有两种方法：
- 从 $i-1$ 往上走 1 阶
- 从 $i-2$ 往上走 2 阶
所以：
$$ dp[i]=dp[i-1] + dp[i-2]$$
第三步：初值
$$ dp[1]=1, \quad dp[2]=2$$
第四步：基于递推，实现自底向上的代码
int climbStairs(int n) { |
