算法设计与分析-2课案.ppt

第2章 递归与分治策略 学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分有哪些信誉好的足球投注网站技术； （2）大整数乘法； （3）Strassen矩阵乘法； （4）棋盘覆盖； (（5）合并排序和快速排序；) （6）线性时间选择； （7）最接近点对问题； （8）循环赛日程表 减治法 算法功能、性能考虑 高性能计算(HPC)/超级计算机系统 并行算法与超级计算 分治法的设计思想：将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 对程序设计的影响： 多核、多处理机上的多线程编程 ——multithread programming 算法总体思想 算法总体思想 n T(n/2) T(n/2) T(n/2) T(n/2) T(n) = 将大问题分解为k个子问题，对这k个子问题分别求解。 对这k个子问题分别求解时，如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 n T(n) = 各小规模的子问题独立求解 将求出的子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 n T(n) = 分治法的前提 大问题分解为子问题后，各个子问题可以独立（并行、同时）求解，相互间无直接交互、依赖关系 子问题解的（简单）合并，可以得到原问题的解 2.1 递归(recursion)的概念 递归函数: 用函数自身给出定义的函数。 递归算法:直接或间接地调用自身的算法 分治vs 递归 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 递归还可以用于描述以自相似方法重复事物的过程， e.g.两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的 例1 阶乘函数 阶乘函数可递归地定义为： 边界条件 递归方程 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。 例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为： 边界条件 递归方程 第n个Fibonacci数可递归地计算如下： int fibonacci(int n) { if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); } 算法复杂性 O(2n) 例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n，m)定义如下： 问题：如何定义1个增长特别快的函数？——Ackerman函数 递归函数的展开 前2例中的函数都可以找到相应的非递归方式定义： Ackerman函数却无法找到非递归的定义: A(n，m)的自变量m的每一个值都定义了一个单变量函数： m=0时，A(n,0)=n+2 m=1时， A(n,1)=A(A(n-1,1),0) = A(n-1,1) + 2， A(1,1)=2 , 故 A(n,1)=2*n m =2时， A(n,2)=A( A(n-1,2) ,1) = 2*A(n-1,2)， A(1,2)=A( A(0,2), 1)= A(1,1) = 2， 故 A(n,2)= 2n 类似的可以推出，m=3时，A(n,3) = , , 2的层数为n m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数 单变量Ackerman函数 单变量的Ackerman函数A(n): A(n)=A(n，n) 定义其拟逆函数α(n)为： α(n)=min{k｜A(k)≥n} ,即α(n)是使n≤A(k)成立的最小的k值 α(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4(什么含