数据结构与算法概要.pptx

《数据结构与算法概要.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法概要.pptx（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。第1页/共113页将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想算法总体思想算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模

2、足够小，很容易求出其解为止。第2页/共113页算法总体思想n对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4

3、)T(n/4)n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。第3页/共113页算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)

4、T(n/4)T(n/4)T(n/4)第4页/共113页算法总体思想n将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)分治法的设计思想是，将一个难

5、以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破，分而治之。分而治之。第5页/共113页2.1 2.1 递归的概念递归的概念递归的概念递归的概念直接或间接地调用自身的算法称为递归算法递归算法。用函数自身给出定义的函数称为递归函数递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用

6、在算法设计之中，并由此产生许多高效算法。第6页/共113页2.1 2.1 递归的概念递归的概念递归的概念递归的概念例例1 1 阶乘函数阶乘函数 非递归定义：非递归定义：n n！=n*(n-1)*(n-2)*1=n*(n-1)*(n-2)*1 阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。第7页/共113页n递归算法：int recur(int n)if(n=1)return 1;return n*recur(n-1);递归出口递归调用第8页/共113页小兔子问题一般而言，兔子在出生两个月后，就有繁殖能力

7、，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？经过月数：-1-2-3-4-5-6-7-8-9-10-11-12兔子对数：-1-1-2-3-5-8-13-21-34-55-89-144第9页/共113页2.1 递归的概念例例2 Fibonacci2 Fibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：int fibonacci(int n)if(n m1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1m-1

8、的划分组成。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。2.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。第17页/共113页2.1 递归的概念例例5 5 整数划分问题整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整

9、数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。正整数n的划分数p(n)=q(n,n)。第18页/共113页2.1 递归的概念例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1

10、和2的前提下，可将圆盘移至a,b,c中任一塔座上。第19页/共113页以四个盘子为例移动N个圆盘的过程包括:2次移动N-1个圆盘的过程1次移动1个圆盘的过程第20页/共113页void hanoi(int n,int a,int b,int c)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);表示以塔座b为辅助塔座，将塔座上自下而上，由大到小叠在一起的-1个圆盘按规则移至塔座上并按同样顺序叠放。将塔座a上的圆盘移动到塔座b上去第21页/共113页Hanoi塔问题的复杂性分析=1移动次数（）移动次数（）移动次数（）移动次数（）当时移动次数（）

11、？第22页/共113页“世界末日问题”1264abc印度布拉玛神庙中的僧人第23页/共113页“世界末日”的推算假定该僧人每秒将一个圆盘从一个塔座移动到另一个塔座完成整个工作的时间 64（秒）18,446,744,073,709,551,615（秒）58505850亿年第24页/共113页算法复杂性同与运算能力的关系算法复杂性C1可解规模N1C2可解规模N2N1与N2的关系lognN11N21N21=N111000nN12N22N22=1000*N12nlognN13N23N231000*N13n2N14N24N24=31.62*N142nN15N25N25=9.963+N15n!N16N26

12、N26 N16假定一个问题有六种不同的算法，算法复杂度分别是（logn,n,nlogn,n2,2n,n!)这六种算法在低速计算机C1和比C1速度快1000倍的计算机C2上运行，N1和N2分别为这六种算法在C1和C2上的可解规模第25页/共113页递归小结优点：优点：结构清晰，可读性强，而且容易用结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。为设计算法、调试程序带来很大方便。缺点：缺点：递归算法的运行效率较低，无论是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比耗费的计算时间还是占用的存

13、储空间都比非递归算法要多。非递归算法要多。第26页/共113页n求Fibonacci数时有很多重复工作：第27页/共113页解决方法：解决方法：在递归算法中消除递归调用，使其在递归算法中消除递归调用，使其转化为非递归算法。转化为非递归算法。1 1、采用一个用户定义的栈来模拟系统的递归调、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，归，只不过人工做了本来由编译器做的事情，优化效果不明显。优化效果不明显。2 2、用递推来实现递归函数。、用递推来实现递归函数。3 3、通过、通过变换能变换

14、能将一些递归转化为尾递归，从而将一些递归转化为尾递归，从而迭代求出结果。迭代求出结果。后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善，但其适用范围有限。但其适用范围有限。递归小结第28页/共113页分治法的基本思想分治法的基本思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立并且与原问题相同。通过递归地求解这些子问题，然后再将各个子问题的解合并，就可以实现对原问题的求解。第29页/共113页分治法的求解过程分治法的求解过程分解(divide)：将原问题分解为一系列子问题；递归求解(conquer)：递归求解各个子问题。若子问题足够小，则直接求解。

15、合并(merge)：将子问题结果合并成原问题的解说明：某些问题不需要合并，比如二分搜索问题第30页/共113页divide-and-conquer(P)if(|P|=n0)adhoc(P);divide P into smaller subinstances P1,P2,Pk;for(i=1,i=k,i+)yi=divide-and-conquer(Pi);return merge(y1,y2,yk);|P|：问题P的规模；adhoc：分治法中的基本子运算n0：阀值如果问题P的规模不超过n0，说明问题已经容易求解，不要再继续分解。利用adhoc(P)直接求解。分治法的设计模式第31页/共113

16、页分治法的分割原则分治法的分割原则实践表明：将一个问题划分成大小相等的k个子问题的处理方法行之有效；通常取k=2第32页/共113页分治法的计算效率分析分治法的计算效率分析通常用递归方程来进行分析分治法将规模为n的问题分成k个规模为n/m的子问题设分解阈值n0=1，且adhoc解规模为1的问题耗费1个单位时间设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题解需要使用f(n)个单位时间。用T(n)表示该分治法divide-and-merge(P)解规模为|P|=n的问题所需要的计算时间第33页/共113页第34页/共113页分治法的适用条件分治法的适用条件分治法的适用条件分

17、治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题可以分解为若干个规模较小的相同问题，即该问题具有该问题具有最优子结构性质最优子结构性质利用该问题分解出的子问题的解可以合并为该问题利用该问题分解出的子问题的解可以合并为该问题的解；的解；该问题所分解出的各个子问题是相互独立的，即子该问题所分解出的各个子问题是相互独立的，即子问

18、题之间不包含公共的子问题。问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法贪心算法或动态规划动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划动态规划较好。第35页/共113页二分搜索技术大整数的乘法Strassen矩阵乘法棋盘覆盖合并排序快速排序线

19、性时间选择最近点对问题循环赛日程表第36页/共113页二分搜索技术二分搜索技术第37页/共113页分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。二分

20、搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。分析：分析：该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。第38页/共113页逐个地扫描数组a中每个元素，直到找到x为止。在含有n个元素的线性表中查找一个元素在最坏情况下都需要进行n次

21、比较，其时间复杂度为O(n)。利用分治法求解此问题,求解过程是：将n个元素分成个数大致相等彼此独立的两半部分，即an/2的前面或后面两个子问题；将第n/2位置的元素与x进行比较，如果相等，则找到x，算法结束。如果xan/2,则在数组a的后半部分继续搜索x；如果xan/2,则在数组a的前半部分继续搜索x。第39页/共113页二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：template int BinarySearch(Type a,const Type&

22、x,int l,int r)while(r=l)int m=(l+r)/2;if(x=am)return m;if(x 0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。第62页/共113页棋盘覆盖void chessBoard(int tr,int tc,int dr,int dc,int size)if(size=1)

23、return;int t=tile+,/L型骨牌号 s=size/2;/分割棋盘 /覆盖左上角子棋盘 if(dr tr+s&dc tc+s)/特殊方格在此棋盘中 chessBoard(tr,tc,dr,dc,s);else/此棋盘中无特殊方格 /用 t 号L型骨牌覆盖右下角 boardtr+s-1tc+s-1=t;/覆盖其余方格 chessBoard(tr,tc,tr+s-1,tc+s-1,s);/覆盖右上角子棋盘 if(dr=tc+s)/特殊方格在此棋盘中 chessBoard(tr,tc+s,dr,dc,s);else/此棋盘中无特殊方格 /用 t 号L型骨牌覆盖左下角 boardtr+s

24、-1tc+s=t;/覆盖其余方格 chessBoard(tr,tc+s,tr+s-1,tc+s,s);/覆盖左下角子棋盘 if(dr=tr+s&dc=tr+s&dc=tc+s)/特殊方格在此棋盘中 chessBoard(tr+s,tc+s,dr,dc,s);else/用 t 号L型骨牌覆盖左上角 boardtr+stc+s=t;/覆盖其余方格 chessBoard(tr+s,tc+s,tr+s,tc+s,s);复杂度分析复杂度分析T(n)=O(4k)渐进意义下的最优算法第63页/共113页合并排序合并排序第64页/共113页合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，

25、分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。void MergeSort(Type a,int left,int right)if(leftright)/至少有2个元素 int i=(left+right)/2;/取中点 mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组b copy(a,b,left,right);/复制回数组a merge和copy可以在O(n)时间内完成，复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法算法mergeSort递归

26、地调用自身，不断将子序列分成两个更小的子序列算法merge合并两个排好序的数组到新数组b中算法copy将合并后的数值段再复制到数组a中第65页/共113页改进合并排序算法n算法mergeSort存在递归过程p它将序列一分为二，直到序列只剩一个元素为止，然后不断合并2个排好序的序列；n改进思路：p将初始序列看出n个长度为1的有序子序列，然后两两归并，得到n/2个长度为2的有序子序列；再两两归并，重复直到得到一个长度为n的有序序列第66页/共113页改进合并排序算法mergeSort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第

27、二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97第67页/共113页快速排序快速排序第68页/共113页快速排序算法的基本思想基本思想对于输入的子数组ap:r，按分治策略的基本步骤进行求解；分解：以aq为基准元素将ap:r划分成三段：ap:q-1、aq和aq+1:r，使得ap:q-1中任何元素aqaq+1:r中任何元素aq递归求解：通过递归调用快速排序算法，分别对ap:q-1 和aq+1:r进行排序；合并：将排序好的ap:q-1和aq+1:r，按照以下方式合并ap:q-1=ap:q-1,aq,aq+1:r第69页/共113页基准元素第70页/共113页

28、一趟排序中，常选取第一个元素为基准元素。低端指针left增大，高端指针right减小，将比基准元素小的元素交换到低端，更大的交换到高端，直到leftright。第71页/共113页快速排序在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。templatevoid QuickSort(Type a,int p,int r)if(pr)int q=Partition(a,p,r);QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,

29、r);/对右半段排序 如何确定如何确定q？第72页/共113页快速排序templateint Partition(Type a,int p,int r)int i=p,j=r+1;Type x=ap;/将 x的元素交换到右边区域 while(true)while(a+i x);if(i=j)break;Swap(ai,aj);ap=aj;aj=x;return j;初始序列6,7,5,2,5,8j-;5,7,5,2,6,8i+;5,6,5,2,7,8j-;5,2,5,6,7,8i+;完成6,7,5,2,5,85,2,5 6 7,8j就是我们所需要确定的q第73页/共113页快速排序算法的复杂性

30、分析快速排序算法的复杂性分析运行时间与划分是否对称有关最坏情况：对于一个包含n个元素的数组，被划分成两个区域，其中一个包含n-1个元素，而另一个中只有一个元素。最好情况：每次划分都产生两个大小为n/2的区域。第74页/共113页 快速排序算法在平均情况下的时间复杂性是快速排序算法在平均情况下的时间复杂性是O(nlogn)通常基于比较的排序算法的算法复杂度是通常基于比较的排序算法的算法复杂度是O(n2)快速排序算法因此得名快速排序算法因此得名第75页/共113页templateint RandomizedPartition(Type a,int p,int r)int i=Random(p,r)

31、;Swap(ai,ap);return Partition(a,p,r);快速排序 快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)第76页/共113页线性时间选择线性时间选择第77页/共113页线性时间选择的基本思想元素选择问题给定线性

32、序集中的n个元素和一个整数k，1kn，要求找出这n个元素中第k小的元素。当k=1时找最小元素；当k=n时找最大元素；当k=(n+1)/2找中位数算法设计思想与快速排序算法的设计思想基本相同，即对输入数组进行递归划分，但操作上只对划分出的两个子数组中的一个进行进一步的递归处理；第78页/共113页Private static Comparable randomizedSelect(int p,int r,int k)if(p=r)return ap;int i=randomizedpartition(p,r);int j=i-p+1;if(k=j)return randomizedSelect(

33、p,i,k);else return randomizedSelect(i+1,r,k-j);说明：为什么只需要对其中的一个子数组进行进一步的递归处理为什么只需要对其中的一个子数组进行进一步的递归处理数组ap:r被划分成两个子数组ap:i和ai+1:r,使得ap:i中的元素都不大于ai+1:r中的元素；计算ap:i中的元素个数j，如果kj,则所要找的元素就在ap:i内，否则在ai+1:r内只要对其中的一个子数组进一步的递归处理即可第79页/共113页对算法select的讨论算法select与randomizedSelect算法相类似，但可以在最坏情况下用O(n)时间完成选择任务randomiz

34、edSelect算法在最坏情况下需要(n2)计算时间，其平均计算时间为O(n)出发点：如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的两个子数组的长度都至少为原数组的倍（0011），那么就可以在最坏的情况下用O(n)时间完成选择任务第80页/共113页说明第81页/共113页寻找满足要求的划分基准按以下步骤寻找满足要求的划分基准1.将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法对每组中的元素进行排序，并取出每组中的中位数，共n/5个。2.递归调用算法select来找这n/5个元素的中位数。如果n/5个为偶数，就找它的两个中位数中较大的一

35、个。以这个元素作为划分基准。注：注：假定假定n个元素都互不相等个元素都互不相等第82页/共113页x选择划分基准选择划分基准第83页/共113页分析满足算法满足算法select的要求的要求第84页/共113页分析分析Select算法将每一组的大小定为5，并选取75作为是否进行递归调用的分界点。这两点保证了T(n)的递归式中两个自变量之和n/5+3n/4=19n/20=an,0a1使T(n)=O(n)的关键*除5和75的组合之外，还有其他选择第85页/共113页算法复杂性分析找中位数的中位数按算法所选基准x进行划分所得到的2个子数组分别至多有3n/4个元素，无论对哪一个子数组调用select都至

36、多用T(3n/4)的时间第86页/共113页Private static Comparable select(int p,int r,int k)if(r-p)5)bubbleSort(p,r);/对数组ap:r进行排序return ap+k-1;/将ap+5*i,p+5*i+4中的第3小元素与ap+i交换位置 /找中位数的中位数，r-p-4，即上面所说的n-5 for(int i=0;i=(r-p-4)/5;i+)int s=p+5*I,t=s+4;for(int j=0;j3;j+)bubble(s,t-j);MyMath.swap(a,p+I,s+2);Comparable x=sele

37、ct(p,p+(r-p-4)/5,(r-p+6)/10);int i=patition(p,r,x),j=i-p+1;if(k=j)return select(p,I,k);else return select(i+1,r,k-j);Select算法流程算法流程第87页/共113页考虑存在相等元素的问题Private static Comparable select(int p,int r,int k)Comparable x=select(p,p+(r-p-4)/5,(r-p+6)/10);int i=patition(p,r,x),j=i-p+1;*对所有等于基准对所有等于基准x的相等元素

38、进行汇总的相等元素进行汇总;如果如果(个数个数m1，且，且jkj+m-1)直接返回直接返回ai;否则否则 调用调用select(i+m+1,r,k-j-m);*第88页/共113页最近点对问题最近点对问题第89页/共113页最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。n在空间交通管制中，若将飞机作为空间中的一个点，则具有最大碰撞危险的两架飞机就是这个空间中距离最接近的一对点。这类问题是计算几何学中一个基本问题。n平面上的最接近点对问题：n给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对距离最小。n基本解决方法：

39、将每个点与其它n-1个点距离算出，找到最小距离。n时间复杂度为：T(n)=n*(n-1)/2+n=O(n2)n分治法：n分解：将空间分成大小近似相等的两个子空间；n求解：递归求解两个子空间内部的最接近点对；n合并：从子空间内部和两个子空间之间最接近点对中选择最接近点对。对这个问题，合并步骤是最复杂的第90页/共113页最接近点对问题给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。u为了使问题易于理解和分析，先来考虑一维一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上

40、某个点m将S划分为2个子集S1和S2，基于平衡子问题平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到能否在线性时间内找到p3,q3？第91页/共113页最接近点对问题u如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。u由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d）

41、，并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果如果(m-d,m中有中有S中的点，则此点就是中的点，则此点就是S1中最大点。中最大点。u因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将从而我们用线性时间就可以将S1的解和的解和S2的解合并成为的解合并成为S的解的解。能否在线性时间内找到能否在线性时间内找到p3,q3？问题：问题：m的选取的选取问题：m的选择第92页/共113页最接近点对问题u类似快速排序法的基准元素选取，如果分割点m选取不当，会造成|S1|=1，|S2|=n-1的情形，使得T(n

42、)=T(n-1)+O(n)=O(n2)u可以通过“平衡子问题”方法加以解决，比如选取各点坐标的中位数作为分割点。问题：问题：m的选取的选取问题：m的选择第93页/共113页Public static double cpair1(S)n=|S|;if(nm；/构造S1和S2 d1=cpair1(S1);d2=cpair1(S2);p=max(S1);q=min(S2);d=min(d1,d2,q-p);return d;第94页/共113页下一步工作一维空间的最近一维空间的最近点对问题点对问题二维空间的最近二维空间的最近点对问题点对问题第95页/共113页P1P2d2d1lddS1S2距离直线距

43、离直线l的距离小于的距离小于d的所有点的所有点直线：x=m其中m为S中各点x坐标的中位数SS1=pS|x(p)mS2=pS|x(p)m说明：说明：递归地在S1和S2上求解最近点对问题，分别得到S1和S2中的最小距离d1和d2，其中d=mind1,d2如果中的最近点(p,q)间的距离d，则p、q必分属S1和S2（假定pS1，qS2）第96页/共113页二维情况下边界点对的处理P1P2d2d1lddS1S2问题：问题：P1中所有点与中所有点与P2中所有中所有点所构成的点对都需要考虑点所构成的点对都需要考虑在最坏情况下，需要处理在最坏情况下，需要处理n2/4个候选点对个候选点对第97页/共113页思

44、考这个问题：思考这个问题：能否在保证找到最近点对的前提下能否在保证找到最近点对的前提下减少需要处理的候选点对数目？减少需要处理的候选点对数目？对候选点对的选取：对候选点对的选取：分析的出发点：分析的出发点：由于P1中的任意一点p，如果它与P2中的点q构成最近点对的候选点对的话，那么必定满足：distance(p,q)d可以，利用点点散布上的稀疏散布上的稀疏性质性质第98页/共113页lddddP1P2pR包含点包含点q q的的d d2d2d矩形矩形R R分析：分析：满足最近点对的候选条件的点满足最近点对的候选条件的点必定落在必定落在d*2d的矩形中的矩形中推论：推论：由于由于P2中任意两点的距

45、离中任意两点的距离dd，所以所以矩形中最多只有个中矩形中最多只有个中的点的点推论可靠吗？推论可靠吗？第99页/共113页推论的正确性分析推论的正确性分析出发点：利用反证法假定在矩形中有超过个中的点d/2d/2dd2d/32d/32d/3分析：分析：（）在个(d/2)*(2d/3)的矩形中，必定有一个矩形中存在个或两个以上的中的点根据鸽舍原理（）由（），我们假定u,v是位于同一个(d/2)*(2d/3)的矩形中两个中的点，两个点间的距离为第100页/共113页推论正确：推论正确：即对于即对于P1中的每个中的每个S1上的点上的点p，最多只，最多只要检查要检查S2中的个点即可。中的个点即可。新问题：

46、新问题：这个点如何确定？这个点如何确定？第101页/共113页对个点的确定解决方案将P1和P2中所有S中的点按其y坐标进行排序，则对P1中的所有点，对排好序的点列进行一次扫描，就可以找出所有最近点对的候选点对。对P1中的每个点最多只需要检查P2中排好序的相继个点。第102页/共113页算法复杂性分析该算法由该算法由Preparata和和Shamos在在1985年提出年提出Preparata F.P.,Shamos M.I.,Computational Geometry:An Introduction.New York:Springer-Verlag,1985第103页/共113页算法改进算法改

47、进出发点:在不改变现有的分治策略的前提下，算法复杂性的降低只能通过进一步减少候选点对的数目来实现；问题：问题：能否在保证找到最近点对的前提下再进一能否在保证找到最近点对的前提下再进一步减少需要处理的候选点对数目？步减少需要处理的候选点对数目？第104页/共113页通过观察，我们可以发现：对于点来说，最多只需要检查最多只需要检查右半带域中的个点（即其坐右半带域中的个点（即其坐标与最近的最多个点即可，标与最近的最多个点即可，上下个个）上下个个）第105页/共113页改进算法的复杂性分析该算法是由周玉林，熊腾荣和朱洪于年提出周玉林周玉林 熊腾荣熊腾荣 朱洪朱洪,“求平面点集最近点对的一个改进算法求平

48、面点集最近点对的一个改进算法”，计算机研究与，计算机研究与发展，发展，Vol.35,No.10,Oct.1998,pages:956-960可以从可以从“/算法分析算法分析/参考资料参考资料/”处下载处下载第106页/共113页进一步考虑的问题二维空间的最近二维空间的最近点对问题点对问题三维空间的最近三维空间的最近点对问题点对问题第107页/共113页循环赛日程表循环赛日程表第108页/共113页问题描述问题描述设有n=2k个运动员要进行网球循环赛。现需要设计一个满足以下要求的比赛日程表：1.每个选手必须与其他n-1个选手各比赛一次；2.每个选手一天只能比赛一次；3.循环赛共进行n-1天；第109页/共113页算法思想算法设计思想根据分治策略，将所有选手分成两半，这样n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归采用这种二分策略，直到只剩下个选手。第110页/共113页考虑当n=8时的情况第111页/共113页课后作业习题 2-8，2-9，2-10，2-27，2-30，2-31，2-32。第112页/共113页感谢您的观看！第113页/共113页