1 渐进符号

1.1 符号

存在常数与，对所有的，满足 。的复杂度最多与一个数量级，即小于等于。

例：

宏
出现在公式中的集合符号(如)表示集合中的某一个函数，而不是集合整体。

例1：
直观理解：表示了一个误差界限，即主要是由构成的，但也有一些的低阶项
实际含义：存在一个函数，使得

例2：
直观理解：“=”应该理解成“是”，而不是“等于”。等号左边隐含任意量词，等号右边隐含存在量词，
实际含义：对于任意函数，总存在函数，使得
用途： 如果有很长的“等式链”，第一个就等于最后一个（只能从左到右，因为是非对称的）

 

1.2  符号

   

 存在常数与，对所有的，满足成立。的复杂度最少与一个数量级，即大于等于。

例：

 

1.3 符号

，表示的复杂度既大于等于的复杂度，又小于等于的复杂度，即于的复杂度相当。

例：,     

 

1.4 和符号

更“严格的”和，不等式需要对所有的c成立，而不仅仅是一个特定的c

类比

 

2 求解递归的三种方法

2.1 代换法

第一步：猜答案Guess the form of the solution。代换法在大多数情况下是有效的，但是不幸的是第一步需是猜答案。你不需要完全猜出来，你可以不需要知道常数系数确切是多少，仅需要猜它的形式。

第二步：通过数学归纳法验证第一步才出来的form是否满足条件。

第三步：也是第二步的必然结果，如果猜对了那么很容易解出常数系数。

下图所示是如何利用代换法解一个递归式：

证明  

那么，上图中证明了小于等于一个常数乘以。图中所解出的答案就是上界，不过不是严格的上界，事实上我们认为也成立。所以这并不能证明递归式的答案就是，这只是表示至多是。

证明  

改进归纳假设

考虑低阶项！！

 

2.2 递归树法

将抽象递归表达式具体化的最佳图形表示就是递归树。该模型以输入规模为n开始，一层层地分解，直到输入规模变为1为止。而这个时候的解决方案已经是琐细的了。图3-5为表达式T(n) = T(n /4) + T(n / 2)+ n2 的递归树。

 各棵树的叶子节点数不一样，因为递归速度不一样。如果按n的子节点为两个n/2，叶子节点数为n，该例子中n的节点为n/4和n/2, 叶子节点数肯定小于n。

 

2.3 主定理法(Master Method) 

每个子问题的规模相同，a个相同的子问题。

     where   ， 是不参与递归的复杂度函数

判断与的大小关系（是递归树叶子节点的数量）：

1. 若对某个常数, 有,  则
2. 若， 则
3. 若对某个常数， 有，且对某个常数和所有足够大的有,

分别举出了主定理方法的三个应用场景的例子以及一个主定理方法不适用的例子。

 

 

证明主定理：

树高度为

 叶子节点数

case 3 : 如果, 代价由上到下呈几何级数降低，最顶层的代价占主导地位，所以，。

case1:   代价由上到下升高，最底层的代价占主导地位，所以，