递归式求解-代入法
放假没事继续看看算导，关于求解递归式一般使用三种方法：
- 代入法
- 递归树方法
- 主方法
本文主要总结一下在使用代入法求解递归式的方法以及需要注意的点和技巧。
代入式求解递归式一般分为两步：
- 猜测解的形式
- 使用数学归纳法求解出解中的常数$c$的范围，并进行证明
需要注意的点
做出合适的猜测
虽然并没有通用的方法来猜测递归式的正确解，但我们可以根据经验来猜测似曾相识的递归式的解作为我们的猜测。例如如下递归式
$$
T(n) = 2T(\lfloor n/2 \rfloor + 17) + n
$$
当$n$足够大时，$\lfloor n/2 \rfloor$和$\lfloor n/2 + 17 \rfloor$的差距并不大，因此我们可以猜测递归式的解为$T(n) = O(nlgn)$
另一种做出好猜测的方法就是先证明递归式较为宽松的上界($\Omega(n)$)和下界($O(n^{2})$)，然后缩小范围最终收敛到渐进紧确界($O(nlgn)$)。
减去低阶项
有时及时猜测出了递归式解的渐进界，但是归纳证明的时候会失败，这常常是因为归纳假设不够强，无法证明出准确的界。这是可以通过在之前的猜测的基础上减去一个低阶的项，归纳证明往往能顺利进行。
例如如下递归式：
$$
T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1
$$
从递归式中我们可以看到问题的划分成两个子问题，但是子问题的规模也是原问题的1/2，因此可以猜测此递归式的渐进解为$O(n)$, 即$T(n) \le cn$
归纳证明:
$$
T(n) \le c\lfloor n/2 \rfloor + c\lceil n/2 \rceil + 1 = cn + 1
$$
显然无法归纳证明，这时候我们可以将猜测的解减去一个低阶项，$T(n) \le cn - d$, 这样便有
$$
T(n) \le (c\lfloor n/2 \rfloor - d) + (c\lceil n/2 \rceil -d) + 1 = cn - 2d + 1
$$
当$d \ge 1$时，便有 $T(n) \le cn - d$.
要显式的证明不等式
这一点其实需要对渐进符号有个正确的理解，渐进符号本身便是一种满足不等式条件的函数集合，因此我们在求解递归式的时候，不能直接证明$T(n) = O(n)$, 因为这样我们并没有证明出以归纳假设严格一致的形式。例如：
$$
T(n) \le 2(c\lfloor n/2 \rfloor) + n \le cn + n = O(n)
$$
这样是错误的，我们必须要显式的的证明$T(n) \le cn$ 才行！
改变变量
有时候递归关系式看起来比较复杂，但是经过变量替换便可以讲一个未知的递归式变成熟悉的形式。例如：
$$
T(n) = 2T(\lfloor \sqrt{n} \rfloor) + lgn
$$
我们令$m = lgn$ 则 $\sqrt{n} = 2^{m/2}$
$$
T(2^{m}) = 2T(2^{m/2}) + m
$$
使$S(m) = T(2^{m})$, 得到
$$
S(m) = 2S(m/2) + m
$$
这样，此递归式的形式我们在熟悉不过了，我们便可以得到$S(m) = O(mlgm) = T(2^{m})$
令$m = lgn$代入，得到
$$
T(n) = O((lgn)(lglgn))
$$
练习
证明: $T(n) = T(\lceil n/2 \rceil) + 1$ 的解为 $O(lgn)$
根据递归关系式有:
$$
T(n) \le clg(\lceil n/2 \rceil) + 1 \le clgn + 1
$$
显然无法证明，这时我们尝试让解减去一个低阶项$d$, 即$clgn - d$
$$
T(n) \le clg(\lceil n/2 \rceil) - d + 1 \le clg(n) - d + 1
$$
取$d \ge 1$ 则有
$$
T(n) \le clgn
$$
然后是边界条件，我们这里假设$T(1) = 1$则有$T(1) \le clg1 - 1 = -1 \ne 1$ 矛盾。
由于渐进符号仅要求我们的$n \ge n_{0}$就可以，因此我们可以尝试下$T(2) = 2$, 这样则有, 当$c \ge 3$
$$
T(2) = 2 \le clg2 - 1 = c - 1
$$
因此完成归纳证明：对于$c \ge 3$， $n \ge 2$ 有 $T(n) \le clgn - 1$, 即$T(n) = O(lgn)$