Substitution method
- Guess the form of the solution.第一步，猜解。
- Use mathematical induction to find the constants and show that the solution works.第二步，将解代入检验是否正确。
上面就是Substitution的基本过程，其实挺简单的，但是我在理解这个“数学归纳法”的时候还是出现了偏差，在高中的时候我们学习的“数学归纳法”是这样的：
1.假设当n=k-1时情况成立，推出当n=k时情况也成立。(就像一个多米诺骨牌一样，1倒了，后面的数都跟着倒了)
2.证明base case成立，证毕。
我刚开始的时候以为这里的“数学归纳法”是这么证明的：
- 假设当n=k/2时情况成立，推出当n=k时情况也成立。
- 证明base case成立，证毕。
我心想这肯定是不成立的啊，T(1)成立，推出T(2),T(4)...，(也就是说多米诺骨牌中其中有些数并没有倒),那T(3)如何证明呢？我在这个问题上纠结了很久。
后面去和同学(感谢yb同学)探讨了一下才知道其实这里的“数学归纳法”是“第二数学归纳法”，而我们高中通常用的是“第一数学归纳法”，所谓的“第二数学归纳法”是：
- 假设当n<k时情况成立，推出当n=k时情况也成立。
- 证明base case成立，证毕。 第二数学归纳法是假设n<k时成立，有人或许会有疑问说这个假设太赖皮了吧，以前我们都只是假设n=k-1时情况成立，这里直接就假设n<k时都成立了，其实这样的假设一点问题都没有，我们甚至能用第一数学归纳法推出第二数学归纳法， 这里就不详细展开了。总之，这里的数学归纳法的过程是这样的：
- 假设当n<k时情况成立，当n=k/2时,推出当n=k时情况也成立。(不管你用n<k的哪个数推出n=k情况成立都可以，这里我们恰好能用n=k/2时的情况推出n=k情况成立)
- 证明base case成立，证毕。
下面还有几个使用Substitution需要注意的点。
Subtleties
意为微妙的细节，也就是有一些tricky的地方，有的时候我们会发现证明的时候刚好差一点常数就能证明T(n)<=f(n)了，就差了那么一点，比如下面这种情况：
我们很自然的猜测T(n)<=cn，于是：我们假设T(n/2)<=cn/2,得到：
于是我们会想能不能使条件变得更“宽松”一点，以便于我们代入验证，于是我们假设`T(n/2)<=cn/2-d，就可以用以下方式证明。
这里的微妙之处在于，我们其实使假设的条件变得更“严苛”了，也就是更“弱”了,当时这样反而让我们证明出了结论。
Avoiding pitfalls
试看以下的证明：
错误的证明！为什么？因为它并未严格的证明T(n)<=cn。
Recursion-tree method
Recursion-tree method通常是与Substitution method配合使用的，即用Recursion-tree method猜解，然后用substitution method证明。当然如果你能很详细的画出recursion-tree，直接把这个过程当作证明也是可以的。 这个就不重点提了。
Master method
书上的原话是这么说的：
The master method provides a “cookbook” method for solving recurrences of the form
T(n)=aT(n/b)+f(n)。
所谓“菜谱”式的解决方案，其实就是为那种形式的递归式建立了模型，以便快速方便的解决此类递归式。
上面就是所谓的Master method，挺容易理解的，也和我们的“主观感受”相同，但是这里有一些技术细节需要了解：
- 这里的g(x)>f(x)，必须是
多项式大于，而不是渐进大于，比如n^1.1既渐进大于n，也多项式大于n，nlogn渐进大于n，但是并不多项式大于n，渐进大于比的其实就是增长速度，而多项式大于不一样， 为什么nlogn不渐进大于n？因为对于c>0, n^c>logn，也就是说，logn比任意的n^c都小，所以logn在多项式级别上其实并没有贡献。 - 关于第3种情况的正则条件，这个条件我暂时还没找到反例，(先挖个坑，看以后能不能填)，如果读者知道这个正则条件是什么意思的话可以在评论告诉我，谢谢！