算法导论<2、渐近符号、递归及解法>
1、渐记符号、函数、运行时间：
渐记符号实际上应用于函数；用渐记符号来描述算法的运行时间；
2、等式和不等式中的渐近符号
函数中匿名函数的数目可以理解为等于渐近记号出现的次数。
3、标准记号与常用函数
- 3.1、单调性；
- 3.2、向上取整和向下取整；
- 3.3、横运算：取模运算；
- 3.4、多项式：有界性；
- 3.5、指数、对数、阶乘；
- 3.6、多重函数、多重对数函数、
- 3.7、斐波那契数；
4.递归式：一组等式或不等式
它所描述的函数是在更小的输入下该函数的值来定义的。例如 归并排序Merge-Sort 的最坏情况运行时间 T(n)可以用以下递归式来表示：
递归式的解法：代换法、递归树方法、主方法。
- 代入法(Substitution method)
步骤：
（1）、先猜测解的形式（靠经验）；
（2）、用数学归纳法求出解中的常数，证明该猜测的正确性（若出问题，一般应该是假设不够强）。
Eg：
注：避免陷阱：
- 递归树方法(Recursion-tree method)
用途：画一个递归树是一种得到好猜测的直接方法。
分析：在递归树中，每一个结点表示一个单一子问题的代价，子问题对应某次递归函数调用。将递归树中每一层内的代价
相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。
- 主方法(Master method)
Eg：