线性时间选择-yangsong

《线性时间选择-yangsong》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机算法设计与分析题目：线性时间选择问题院（系）：数学与计算机学院年级专业：信息与计算科学姓名：杨松学号：201210802023指导教师：鄢莉二〇一四年十一月十九日攀枝花学院教务处制一、实验目的：熟悉掌握分治算法设计技术二、实验内容：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。对于线性序列集合中元素个数比较少的情况，可以先排序，再选择这n个元素中第k小的元素。但排序的时间复杂度最好是O(nlogn)。如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最

2、坏情况下用O(n)时间完成选择任务。三、实验要求：1、按教材所授内容要求，完成“线性时间选择问题”算法。得到一个完整正确的程序。2、问题规模：不少于20003、输出最终结果。四、实验设备：Windows7系统、VisualC＋＋五、算法分析：将n个输入元素划分成én/5ù个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共én/5ù个。递归调用select()来找出这én/5ù个元素的中位数。如果én/5ù是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。设所有元素互不相同。在这种情况下，找出的基准x至少比3

3、(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。按照此法计算所花费时间为：T(n)=O(n)三、程序源码：#include#includeusingnamespacestd;templatevoidSwap(Type&x,Type&y);inlineintRandom(intx,inty);template

4、assType>intPartition(Typea[],intp,intr);templateintRandomizedPartition(Typea[],intp,intr);templateTypeRandomizedSelect(Typea[],intp,intr,intk);intmain(){voidSelectionSort(inta[]);ints;inta[2000];intb[2000];for(inti=0;i<2000;i++){a[i]=b[i]=rand()%10000;cout<

5、<voidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}inlineintRandom(intx,inty){srand((unsigned)time(0));intran_nu

6、m=rand()%(y-x)+x;returnran_num;}templateintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]x);if(i>=j){break;}Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}templateintRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);S

7、wap(a[i],a[p]);returnPartition(a,p,r);}templateTypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r){returna[p];}inti=RandomizedPartition(a,p,r);intj=i-p+1;if(k<=j){returnRandomizedSelect(a,p,i,k);}else{//由于已知道子数组a[p:i]中的元素均小