绪论以及递归式上界函数的证明
循环不变式
循环不变式主要用来证明算法的正确性。
其定义是：第一次进入循环前成立，之后每次循环还成立的关系。
证明其大概分为下面三个过程：
初始：进入循环前成立
保持：每次循环之后成立
终止：循环能在有限次结束
总结前两步类似于数学归纳法，第三步保证有穷性。
限界函数相关
3个符号，渐进紧确界、上界函数、下界函数。
如何求解递归式的限界函数？
代换法：
这里值得注意的是带入那一步，是后续推导的关键既是合理的令m。
最后的结果需要在边界条件下考虑是否成立。
递归树法
画树求和，用来猜测解的形式，还是要落入代入法
主方法
实际上既是f（n）与logb的a比较大小取较大值；相等即为情况2。
但是主要这大于小于是多项式的小于大于，其间的差距必须是n的倒3次方。我们知道在这之间lgn小于n的倒3次方，值得注意。