第2章递归与分治策略
1、什么是递归?
2、掌握和理解求n!函数的递归程序。该递归的终止边界条件是什么？
3、掌握和理解Fibonacci数列的递归程序，并能编写辅助空间为3个单元的非递归算法。该递归的终止边界条件是什么？
4、掌握和理解求数列全排列的递归程序。该递归的终止边界条件是什么？
5、掌握和理解整数划分问题的递归程序。该递归的终止边界条件是什么？
6、掌握和理解Hanoi塔问题的递归程序。该递归的终止边界条件是什么？
7、深刻理解分治法的基本思想。
8、掌握和理解分治法的时间复杂度求解的递归和非递归方程，并理解方程中，各个参数的含义，对于给定的分治算法，能够运用方程，求出其时间复杂度。
9、理解和掌握二分搜索技术的实现及时间复杂度的计算。
10、理解大整数乘法和矩阵乘法的分治策略，体会简单的分治也许并不能得出更好地方案，还需加上适当的技巧，才能切实提高算法效率。
11、理解和掌握棋盘覆盖问题的分治算法及时间复杂度的计算。
12、理解和掌握合并排序分治算法的递归实现，并能改造实现求数列逆序对数量的分治算法。
13、能够写出合并排序分治算法的非递归实现，并能改造实现求数列逆序对数量的分治算法。
14、掌握和理解快速排序分治算法的实现。
15、掌握和理解求第k小元素的仿快排算法。
16、掌握和理解求第k小元素时间复杂度为O(n)的改进算法
17、掌握和理解最接近点对问题的算法。
算法分析(第二章)：递归与分治法 一、递归的概念 知识再现：等比数列求和公式： 1、定义：直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 2、与分治法的关系： 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。 3、递推方程： (1)定义：设序列01,....n a a a简记为{ n a}，把n a与某些个() i a i n <联系起来的等式叫做关于该序列的递推方程。 (2)求解：给定关于序列{n a}的递推方程和若干初值，计算n a。 4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序 5、优缺点： 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 二、递归算法改进： 1、迭代法： (1)不断用递推方程的右部替代左部 (2)每一次替换，随着n的降低在和式中多出一项 (3)直到出现初值以后停止迭代 (4)将初值代入并对和式求和 (5)可用数学归纳法验证解的正确性 2、举例： -----------Hanoi塔算法----------- ---------------插入排序算法----------- ()2(1)1 (1)1 T n T n T =?+ = ()(1)1 W n W n n W =?+? （1）=0