基础知识学习笔记

1、如果函数f(n)的渐近的上界和下界相等，都是g(n)，这时称g(n)是f(n)的渐近的紧的界，或者称函数f(n)的阶是g(n)。同阶可称g(n)是f(n)的紧的界。

2、大O记号和小o记号的区别：

当f(n)=O(g(n))时，f(n)的阶可能低于g(n)的阶，也可能等于g(n)的阶，而f(n)=o(g(n))时，f(n)的阶只能低于g(n)的阶。因此f(n)=o(g(n))可以推出f(n)=O(g(n))，但是反过来不成立。

3、主定理

4、指数函数的阶高于多项式函数的阶，而多项式函数的阶高于对数函数的阶。

5、在没有明确说明的情况下，算法课程中的 "log n" 通常意味着二进制对数。

6、在使用主定理（Master Theorem）来分析递归算法的时间复杂度时，我们关注的是当问题规模n趋向于无穷大时，时间复杂度 T(n)的渐近行为。

7、递推方程不满足主定理的条件，可以使用递归树求解。

8、在递归算法的时间复杂度分析中常常用到主定理，其中a代表递归调用所产生的字问题个数，n/b代表这些字问题的规模，f(n)则代表调用前的操作及调用后把子问题的解组合成原问题的解的总工作量。

9、递归树方法：

10、复杂度的递归求解

1.展开法：通过直接对递归的展开计算复杂度；
2.代入法：先猜测解的形式，再通过数学归纳浅证明；
3.递归树方法：通过画递归树的方法来求解，因这种方法适用性比较好，所以是最重要的方法；
4.主方法针对T（n）=aT（n/b）+f（n）的形式，主方法给出了相关的规律，所以主方法是最简单的方法（套规律就行），但因只能针对上面形式的递归式，所以适用性较差。