目录

 

1.4  算法分析

 

1.4.1  算法分析

 

1.4.2  迭代VS级数

 

1.4.3  迭代与递归

1.4.3.1  线性递归

数组求和（迭代）

数组求和（线性递归）

减而治之

 

1.4.3.2  递归分析

递归跟踪

递推方程

 

1.4.3.3  递归模式

多递归基

多向递归

 

---

1.4  算法分析

 

1.4.1  算法分析

1. 算法分析主要有两个任务： 

        正确性

        复杂度

2. 复杂度的分析方法有三种： 

        迭代式算法：级数求和

        递归式算法：递归跟踪 + 递归方程

        猜测 + 验证

3. 算数级数：与末项的平方同阶 

4. 幂方级数：比幂次高出一阶 

5. 几何级数(a>1)：与末项同阶 

6. 收敛级数：O(1)

7. 可能未必收敛，但长度有限 

8. 循环：一般随着层数的增加指数式增长

9. 递归跟踪分析：检查每个递归实例，累计所需时间（调入语句本身，计入对应的子实例），总和即为算法执行时间。

 

1.4.2  迭代VS级数

 

1.4.3  迭代与递归

算法的两种思想方法：分而治之，减而治之。
        分而治之：将一个问题分两个规模大小差不多的子问题。
        减而治之：将一个问题分为一个子问题和一个规模缩减的问题。

 

1.4.3.1  线性递归

数组求和（迭代）

空间复杂度见我的上一篇绪论（3），在没有专门说明时，凡是在讨论空间复杂度，都不考虑输入所需的空间，只考量另外的用于计算所必须那些空间的总量。

数组求和（线性递归）

减而治之

递归每深入一层，待求解问题的规模都会缩减一个常数，直至最终蜕化为平凡的小（简单）问题，当抵达递归基时，算法将执行非递归的计算。

 

1.4.3.2  递归分析

递归跟踪

用于分析递归算法的总体运行时间与空间。将递归算法的执行过程整理为图的形式：

1.算法的每一递归实例都表示为一个方框，其中注明了该实例调用的参数

2.若实例M调用实例N，则在M与N对应的方框之间添加一条有向联线

具体的过程图如下  ：

 

递推方程

与递归跟踪相反，该方法无需绘出具体的调用过程，而是通过对递归模式的数学归纳，导出复杂度定界函数的递推方程（组）及其边界条件，从而将复杂度的分析，转化为递推方程（组）的求解。

总体思路上，该方法与微分方程法类似 ： 很多复杂函数的显式表示通常不易直接获得，但它们的微分形式却遵循某种相对简洁的规律，通过求解描述这些微分方程，即可最终导出原函数的显式表示。而微分方程的解通常并不唯一，除非给定某些边界条件。类似的，为使复杂度定界函数的递推方程能给出确定的解,也需要给定某些边界条件。

 

1.4.3.3  递归模式

多递归基

多向递归

递归算法中,不仅递归基可能有多个,递归调用也可能有多种可供选择的分支,在后面二分递归给出实例。书上P20 ==> P21有一个计算幂函数power(2,n)的例子。