当将归纳假设应用于较小的值时，我们将猜测的解代入函数，因此得名“代入法”。这种方法很强大，但是我们必须能够猜出解的形式，以便将其代入。 我们可以用代入法为递归式建立上界或者下界。例如我们确定下面递归式的上界：
T
(
n
)
=
2
T
(
⌊
n
/
2
⌋
)
+
n
(
1.1
)
T(n)=2T(\lfloor n/2\rfloor)+n \qquad \qquad(1.1)
T(n)=2T(⌊n/2⌋)+n(1.1) 我们猜测其解为
T
(
n
)
=
O
(
n
l
g
n
)
T(n)=O(nlgn)
T(n)=O(nlgn)，代入法要求证明，恰当选择常数c>0,可有
T
(
n
)
≤
c
n
l
g
n
T(n)\leq cnlgn
T(n)≤cnlgn。首先假定此上界对所有正数m<n都成立，特别是对于
m
=
⌊
n
/
2
⌋
m=\lfloor n/2 \rfloor
m=⌊n/2⌋，有
T
(
⌊
n
/
2
⌋
)
≤
c
⌊
n
/
2
⌋
l
g
(
⌊
n
/
2
⌋
)
T(\lfloor n/2 \rfloor) \leq c \lfloor n/2 \rfloor lg(\lfloor n/2 \rfloor)
T(⌊n/2⌋)≤c⌊n/2⌋lg(⌊n/2⌋)。我们将其代入到递归式，有
T
(
n
)
≤
2
(
c
⌊
n
/
2
⌋
l
g
(
⌊
n
/
2
⌋
)
)
+
n
≤
c
n
l
g
(
n
/
2
)
+
n
=
c
n
l
g
n
−
c
n
l
g
2
+
n
=
c
n
l
g
n
−
c
n
+
n
≤
c
n
l
g
n
T(n)\leq 2(c\lfloor n/2 \rfloor lg(\lfloor n/2 \rfloor))+n\leq cnlg(n/2)+n \\ =cnlgn-cnlg2+n=cnlgn-cn+n\leq cnlgn
T(n)≤2(c⌊n/2⌋lg(⌊n/2⌋))+n≤cnlg(n/2)+n=cnlgn−cnlg2+n=cnlgn−cn+n≤cnlgn 其中，只要
c
≥
=
1
c\geq=1
c≥=1,最后一步都会成立。 数学归纳法要求我们证明解在边界条件下也成立。为了证明这一点，我们通常证明对于归纳证明，边界条件适合作为基本情况。 对于递归式1.1我们必须证明，通过选择足够大的常数项c，可以使得上界
T
(
n
)
≤
c
n
l
g
n
T(n)\leq cnlgn
T(n)≤cnlgn对边界条件也成立。这一要求可能会产生问题。例如为了方便讨论，假设T(1)=1 是递归式唯一的边界条件。对于n=1，边界条件
T
(
n
)
≤
c
n
l
g
n
T(n)\leq cnlgn
T(n)≤cnlgn推导出
T
(
1
)
≤
c
1
l
g
1
=
0
T(1)\leq c1lg1=0
T(1)≤c1lg1=0,这与T(1)=1矛盾。因此，我们的归纳证明的基本情况不成立。 对于上面这种情况，我们采用如下的对应策略：在递归式1.1中，渐进符号仅要求我们对
n
≥
n
0
n\geq n_0
n≥n0，这样子的话对于n>3也好，n>2也好，归纳法并不是直接以来T(1)。
二、做出好的猜测
然而，比较遗憾的是，并没有通用的方法允许我们去直接猜测得到递归式的正确解。我们需要不断地积累经验。
如果要求解的递归式和你曾经见过的递归式相似，那么我们可以猜测一个类似的解。例如下面的递归式：
T
(
n
)
=
2
T
(
⌊
n
/
2
⌋
+
17
)
+
n
T(n)=2T(\lfloor n/2 \rfloor+17)+n
T(n)=2T(⌊n/2⌋+17)+n 这个看起来比较困难，因为在等式的右边T的参数中增加了17，但是在直观上，增加的这一项并不会显著地影响递归式的解。当n较大时
⌊
n
/
2
⌋
\lfloor n/2 \rfloor
⌊n/2⌋ 和
⌊
n
/
2
⌋
+
17
\lfloor n/2 \rfloor+17
⌊n/2⌋+17的差距并不大，因此我们可以推测T(n)=O(nlgn)
另外一种方案是线证明递归式比较松的上界和下界，然后缩小不确定的范围。例如对于式1.1，我们可以从下界
T
(
n
)
=
Ω
(
n
)
T(n)=\Omega(n)
T(n)=Ω(n)开始，因为递归式中包含着n这一项，还可以证明一个初始上界
T
(
n
)
=
O
(
n
2
)
T(n)=O(n^2)
T(n)=O(n2)。然后，我们就可以逐步地降低上界，提升下界，直到收敛到渐进紧确界
T
(
n
)
=
Θ
(
n
l
g
n
)
T(n)=\Theta(nlgn)
T(n)=Θ(nlgn)。
三、微妙的细节
有的时候，我们可能猜出了正确的递归式解的渐进界，但是莫名奇妙地在归纳证明的时候失败了。问题常常出在归纳假设不够强，无法证出准确的界。当遇到这种障碍的时候，我们将它减去一个低阶的项，数学证明常常就能够顺利地进行。 考虑以下的递归式：
T
(
n
)
=
T
(
⌊
n
/
2
⌋
)
+
T
(
⌈
n
/
2
⌉
)
+
1
T(n)=T(\lfloor n/2 \rfloor)+T(\lceil n/2 \rceil)+1
T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+1 我们猜测解为T(n)=O(n),并且尝试证明对某个恰当选出的常数c，
T
(
n
)
≤
c
n
T(n)\leq cn
T(n)≤cn成立。将我们的猜测代入到递归式，得到
T
(
n
)
≤
c
⌊
n
/
2
⌋
+
c
⌈
n
/
2
⌉
+
1
=
c
n
+
1
T(n)\leq c\lfloor n/2 \rfloor+c\lceil n/2 \rceil +1=cn+1
T(n)≤c⌊n/2⌋+c⌈n/2⌉+1=cn+1 但是这不是我们想要的，这个也并不意味着对于任意的c都有
T
(
n
)
≤
c
n
T(n)\leq cn
T(n)≤cn 从直觉上看，我们的猜测是接近正确的：只差一个常数1，一个低阶项。但是，除非我们证明与归纳假设严格一致的形式，否则数学归纳法还是会失败的。克服这个困难的一个方法是从先前的猜测中减去一个低阶项。 所以新的猜测为
T
(
n
)
≤
c
n
−
d
T(n)\leq cn-d
T(n)≤cn−d，d是大于0的一个常数。我们现在有
T
(
n
)
≤
(
c
⌊
n
/
2
⌋
−
d
)
+
(
c
⌈
n
/
2
⌉
−
d
)
+
1
=
c
n
−
2
d
+
1
≤
c
n
−
d
T(n)\leq (c\lfloor n/2 \rfloor -d )+(c\lceil n/2 \rceil-d )+1 \\ =cn-2d+1\leq cn-d
T(n)≤(c⌊n/2⌋−d)+(c⌈n/2⌉−d)+1=cn−2d+1≤cn−d 只要
d
≥
1
d\geq1
d≥1,此式就成立。与以前一样，我们必须选择足够大的c来处理边界条件。
四、避免陷阱
使用渐进符号很容易出错。例如，在递归式(1.1)中，我们可能错误地“证明”T(n)=O(n)：猜测
T
(
n
)
≤
c
n
T(n)\leq cn
T(n)≤cn，并且论证：
T
(
n
)
≤
2
(
c
⌊
n
/
2
⌋
)
+
n
≤
c
n
+
n
=
O
(
n
)
错
误
!
!
!
T(n) \leq 2(c\lfloor n/2 \rfloor)+n\leq cn+n=O(n) 错误!!!
T(n)≤2(c⌊n/2⌋)+n≤cn+n=O(n)错误!!! 因为c是常数，错误在于我们并未证出与归纳假设严格一致的形式，即
T
(
n
)
≤
c
n
T(n)\leq cn
T(n)≤cn。因此，当要证明
T
(
n
)
=
O
(
n
)
T(n)=O(n)
T(n)=O(n)时，必须要显式地证出
T
(
n
)
≤
c
n
T(n)\leq cn
T(n)≤cn。
五、改变变量
有时，一个小的代数运算可以将一个未知的递归式变成我们所熟悉的形式。例如，考虑如下递归式：
T
(
n
)
=
2
T
(
⌊
n
⌋
)
+
l
g
n
T(n)=2T(\lfloor \sqrt n\rfloor)+lgn
T(n)=2T(⌊n⌋)+lgn 它看起来很困难。但是我们可以通过改变变量来简化它。为了方便起见，我们不必担心值的舍入误差问题，只考虑
n
\sqrt n
n是整数的情形即可。令m=lgn，得到
T
(
2
m
)
=
2
T
(
2
m
/
2
)
+
m
T(2^m)=2T(2^{m/2})+m
T(2m)=2T(2m/2)+m 现在重新命名
S
(
m
)
=
T
(
2
m
)
S(m)=T(2^m)
S(m)=T(2m)，得到新的递归式：
S
(
m
)
=
2
S
(
m
/
2
)
+
m
S(m)=2S(m/2)+m
S(m)=2S(m/2)+m 可以很轻松地求得这个递归式的解为S(m)=O(mlgm)。再从S(m)转换回T(n)，我们得到
T
(
n
)
=
T
(
2
m
)
=
S
(
m
)
=
O
(
m
l
g
m
)
=
O
(
l
g
n
l
g
l
g
n
)
T(n)=T(2^m)=S(m)=O(mlgm)=O(lgnlglgn)
T(n)=T(2m)=S(m)=O(mlgm)=O(lgnlglgn)。
