算法课件资料第2章+递归与分.pptVIP

第2章 递归与分治策略 学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分有哪些信誉好的足球投注网站技术； （2）大整数乘法； （3）Strassen矩阵乘法； （4）棋盘覆盖； （5）合并排序和快速排序； （6）线性时间选择； （7）最接近点对问题； （8）循环赛日程表。 2.1 递归的概念 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 2.1 递归的概念 2.1 递归的概念 2.1 递归的概念 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)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。 M=3时，类似的可以推出 M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。 2.1 递归的概念 定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。 定义其拟逆函数α(n)为： α(n)=min{k｜A(k)≥n}。 即α(n)是使n≤A(k)成立的最小的k值。 α(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4。但在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。 2.2 分治算法总体思想 将要求解的较大规模的问题分割成k个更小规模的子问题。 2.2 分治算法总体思想 将要求解的较大规模的问题分割成k个更小规模的子问题。 分治法的适用条件 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 算法分析题： 2-7，2-13，2-15，2-31 算法实现题： 2-1，2-14 快速排序的复杂度分析（总结）： 2.8 快速排序 最坏时间复杂度：O(n2) 平均时间复杂度：O(nlogn) 辅助空间：O(n) templateclass Type int RandomizedPartition (Type a[], int p, int r) { int i = Random(p,r); Swap(a[i], a[p]); return Partition (a, p, r); } 快速排序的算法改进1： 快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在a[p:r]中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。 2.8 快速排序 快速排序的算法改进2： 由下一节选择问题（节2.9）选择基准元素的方法：中位数的中位数法来改进快速排序，可使快速排序的划分是较为对称的，最坏情况下复杂性：O(nlogn) 2.8 快速排序 2.9 线性时间的选择问题 给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素 当k=1，找最小元素 当k=n，找最大元素 当k处于中间的元素，称为中位数 当n为奇数时，中位数只有1个，k=(n+1)/2； 当n为偶数时，中位数有2个，k=n/2, n/2+1. 1，找最大元素FindMax 算法最坏情况下的时间复杂性为O(n) 2.9 线性时间的选择问题 2，找最大和最小元素FindMaxMin 3，找第二大 举例 计算Fibonacci 数 因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。 这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用 能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，