定义:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。
(1)在某些特殊情况下,很容易设计出解选择问题的线性时间算法。如:当要选择最大元素或最小元素时,显然可以在O(n)时间完成。(一趟比较即可)
(2)一般的选择问题,特别是中位数的选择问题似乎比最小(大)元素要难。但实际上,从渐近阶的意义上,它们是一样的。也可以在O(n)时间完成。
线性时间选择方法一:randomizedSelect
思想:改编随机快速排序,不用把整个数组全部排序,而是选择的排序(更快)
时间复杂度:
(1)在最坏情况下,算法randomizedSelect需要O(n^2)计算时间
eg.要找最小的元素,但是每次进行Partition函数划分时得到的位置总是很大(靠近n)(即总是在最大元素出划分)
(2)但可以证明,算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。
代码如下:
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int Partition(int a[],int p,int r){ int i=p,j=r+1,x=a[p]; while(1){ while(a[++i]<x&&i<r); while(a[--j]>x); if(i>=j)break; swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return j; } int RandomizedPartition(int a[],int p,int r){ int i=rand()%(r-p)+p; swap(a[p],a[i]); return Partition(a,p,r); } int RandomizedSelect(int a[],int p,int r,int k){ if(p==r)return a[p]; int i=RandomizedPartition(a,p,r);//返回基准元素的位置 int j=i-p+1;//表示基准元素及其左边一共多少个元素 if(k<=j)RandomizedSelect(a,p,i,k); else RandomizedSelect(a,i+1,r,k-j); } int main(){ int a[10]={3,1,7,6,5,9,8,2,0,4}; int x; while(scanf("%d",&x)!=EOF){ int ans=RandomizedSelect(a,0,9,x); printf("%d\n",ans); } }
线性时间选择方法二:
如果能在线性时间内找到一个划分基准,使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数),那么就可以在最坏情况下用O(n)时间完成选择任务。
例如,若ε=9/10,算法递归调用所产生的子数组的长度至少缩短1/10。所以,在最坏情况下,算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n) 。由此可得T(n)=O(n)。
老师讲这时,我记得很清,强调了找到而非确定,“找到”是找到我们想要得中位数的值,而我们之前的快排等都是确定值的位置,即把基准元素放到正确的位置上。
步骤:
(1)将n个输入元素划分成n/5(向上取整)个组,每组5个元素,最多只可能有一个组不是5个元素。用任意一种排序算法,将每组中的元素排好序,并取出每组的中位数,共n/5(向上取整)个。
(2)递归调用select来找出这n/5(向上取整)个元素的中位数。如果n/5(向上取整)是偶数,就找它的2个中位数中较大的一个。以这个元素作为划分基准。
划分策略示意图:
白色圆点:每组的中位数; 点x:中位数的中位数
例子:
按递增顺序,找出下面29个元素的第18个元素:8,31,60,33,17,4,51,57,49,35,11,43,37,3,13,52,6,19,25,32,
54,16,5,41,7,23,22,46,29.
(1) 把前面25个元素分为5(=floor(29/5))组: (8,31,60,33,17),(4,51,57,49,35),(11,43,37,3,13),(52,6,19,25,32),(54,16,5,41,7);
(2) 提取每一组的中值元素,构成集合{31,49,13,25,16};
(3) 递归地使用算法求取该集合的中值,得到m=25;
(4) 根据m=25, 把29个元素划分为3个子数组(按原有顺序)
P={8,17,4,11, 3,13,6,19,16,5,7,23,22}
Q={25}
R={31,60,33,51,57,49,35,43,37,52,32,54,41,46,29}
(5) 由于|P|=13,|Q|=1,k=18,所以放弃P,Q,使k=18-13-1=4,对R递归地执行本算法;
(6) 将R划分成3(floor(15/5))组:{31,60,33,51,57},{49,35,43,37,52},{32,54,41,46,29}
(7) 求取这3组元素的中值元素分别为:{51,43,41},这个集合的中值元素是43;
(8) 根据43将R划分成3组:
{31, 33, 35,37,32, 41, 29},{43},{60, 51,57, 49, 52,54, 46}
复杂度:
设数组长度为n
当n<75时,算法select所用的计算时间不超过某一常数C1
当n≥75时,for循环执行n/5次,每次用时为某一常数(固定个数即5个中查找!);select找中位数的中位数,由于长度为原长度的1/5,所以用时可记为T(n/5);划分以后所得到数组至多有3n/4个元素,用时记为T(3n/4)。所以T(n)可以递归表示为:
解此递归式为T(n)=O(n)
上述算法将每一组的大小定为5,并选取75作为是否作递归调用的分界点(大于75使用该算法)。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn,0<ε<1。这是使T(n)=O(n)的关键之处。当然,除了5和75之外,还有其他选择。
注意:
(1)设中位数的中位数是x,比x小和比x大的元素至少3*(n-5)/10个,原因:
3*(n/5-1)*1/2
3---中位数比x小的每一组中有3个元素比x小
n/5-1---有5个数的组数
1/2---大概有1/2组的中位数比x小
(2)而当n≥75时,3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4,也就是说,长度最长为原长度的3/4。
如图,划分的部分左上是肯定比x小的(大概占1/4)右下是肯定比x大的(大概占1/4)左下和右上不确定,就算这两部分同时不比x小或比x大,划分成的子区间也能至少缩短1/4!
核心代码:
Type Select(Type a[], int p, int r, int k) { if (r-p<75) { //用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; }; for (int i=0;i<=(r-p-4)/5;i++)//i即为n个元素的分组个数 //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置; //将中位数元素换至前面 //找中位数的中位数,r-p-4即上面所说的n-5 Type x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);//x是中位数的中位数 int i=Partition(a,p,r,x),j=i-p+1;//i为快排一趟找到区间[p,r]中x应该在的位置,j为[p,i]区间的元素个数 if (k<=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j); }
关键的代码是:
for ( int i = 0; i<=(r-p-4)/5; i++ )//i即为n个元素的分组个数 //将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置; //将中位数元素换至前面
一共(r-p+1)/5个组
注意这里i从0开始表示,为了方便交换时带入数组的下标,0-(r-p-4)/5,即一共(r-p-4)/5+1各组,即(r-p+1)/5个组
代码如下:
#include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<algorithm> using namespace std; void bubbleSort(int a[],int p,int r){ for(int i=p;i<r;i++){ for(int j=i+1;j<=r;j++){ if(a[j]<a[i])swap(a[i],a[j]); } } } int Partition(int a[],int p,int r,int val){ int pos; for(int q=p;q<=r;q++){ if(a[q]==val){pos=q;break;} } swap(a[p],a[pos]); int i=p,j=r+1,x=a[p]; while(1){ while(a[++i]<x&&i<r); while(a[--j]>x); if(i>=j)break; swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; return j; } int Select(int a[],int p,int r,int k){ if(r-p<75){ bubbleSort(a,p,r); return a[p+k-1]; } for(int i=0;i<=(r-p-4)/5;i++){//把每个组的中位数交换到区间[p,p+(r-p-4)/4] int s=p+5*i,t=s+4; for(int j=0;j<3;j++){//冒泡排序,从后开始排,结果使得后三个数是排好顺序的(递增) for(int n=s;n<t-j;n++){ if(a[n]>a[n+1])swap(a[n],a[n-1]); } } swap(a[p+i],a[s+2]);//交换每组中的中位数到前面 } //(r-p-4)/5表示组数-1,则[p,p+(r-p-4)/5]的区间长度等于组数 int x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);//求中位数的中位数 int i=Partition(a,p,r,x),j=i-p+1; if(k<=j)return Select(a,p,i,k); else return Select(a,i+1,r,k-j); } int main(){ int x; //数组a存了0-79 int a[80]={3,1,7,6,5,9,8,2,0,4, 13,11,17,16,15,19,18,12,10,14, 23,21,27,26,25,29,28,22,20,24, 33,31,37,36,35,39,38,32,30,34, 43,41,47,46,45,49,48,42,40,44, 53,51,57,56,55,59,58,52,50,54, 63,61,67,66,65,69,68,62,60,64, 73,71,77,76,75,79,78,72,70,74, }; while(scanf("%d",&x)!=EOF){ printf("第%d大的数是%d\n",x,Select(a,0,79,x)); } }
qwq,博主nc写错输出了,“第i小的数”
更多常见问题的相关技术文章,请访问常见问题教程栏目进行学习!
以上是线性时间选择的详细内容。更多信息请关注PHP中文网其他相关文章!