O(n)时间快速选择

如何在期望线性时间选出第i小的元素?
通过该调用快速排序的random_partition可以实现在平均O(n)时间内选出第i小的元素。
根本原因:这种方法实际上是对数组进行了局部的排序,每次只排序partition后的一半,因为将快速排序的平均时间O(nlogn)降到了O(n).严谨的数学证明请参见《算法导论》。
下面先给出算法的实现,然后叙述缺点及改进。

#include<stdio.h>
#include<stdlib.h>
int partition(int *a,int p,int r);
int random_partition(int *a,int p,int r);
int random_select(int *a,int p,int r,int i);
int main()
{

system("pasue");
return 0;
}
int partition(int *a,int p,int r)
{
	int x=a[r],t;
	int i=p-1,j;
	for(j=p;j<=r-1;j++)
	{
		if(a[j]<=x)//如果要降序排列,则改为if(a[j]>=x)
		{
			i++;
			t=a[i];
			a[i]=a[j];
			a[j]=t;
		}
	}
	t=a[i+1];
	a[i+1]=a[r];
	a[r]=t;
	return i+1;
}
int random_partition(int *a,int p,int r)
{
	int t,i;
	i=p+(int)((r-p+1)*rand()/(RAND_MAX+1.0));//利用随机数随机选择用于分割的元素,注意范围
	t=a[i];
	a[i]=a[r];
	a[r]=t;
	return partition(a,p,r);
}
int random_select(int *a,int p,int r,int i)//找出a[p]——a[r]之间第i小的元素
{
	int q;
	if(p==r)
		return a[p];
	q=random_partition(a,p,r);
	int k=q-p+1;
	if(i==k)
		return a[q];
	else if(i<k)
		return random_select(a,p,q-1,i);
	else
		return random_select(a,q+1,r,i-k);
}

上述算法的时间O(n)是期望的,最坏情况下为O(n*n)。原因在于分割的好坏。下面来说说在最坏情况下仍为O(n)的快速选择算法:
(改写确定性的快速排序的partiton部分)
(1)将数据5个一组分割,每个组内用插入排序找到中位数
(2)再对找到的所有中位数用(1)递归地找它们的中位数
(3)把最终的中位数作为partition的分割元素
这样得到的快速选择算法可以在最坏情况下O(n)的时间效率找到第i小的元素
这样的算法真的是O(n)的吗?关键一点是证明可以在O(n)时间内找到最终的中位数(详细数学证明参见《算法导论》,其中用到了一些技巧^_^)
下面记一下一道题的思路,感觉比较重要。
给出一个O(n)时间的算法,在给定一个有n个不同数字的集合S以及一个正整数k<=n后,它能确定出S中最接近其中位数的k个数。
解:
(1)求出中位数x O(n)
(2)求|S[i]-x|得到SS O(n)
(3)在SS中找第k小的数(具体实现时注意细节) O(n)
(4)搜索ss找出答案(注意要运算回) O(n)

_________________________2017/02/03_______________________________
好吧,把4年前的坑填上。
最坏时间O(n)快速选择算法时间复杂度的证明
设该算法的时间复杂度是T(n)
T(n)<=T(n*1/5)+T(n*7/10)+cn
因为每5个数为一组,则总共找到n*1/5个中位数。从这n*1/5个数中找到中位数本质上就是选第k大数的一个特例,所以是T(n*1/5)。
这n*1/5个中位数中至少有一半的数小于等于最终的中位数,n*1/10
而这n*1/5个数都各自是5个数的中位数,所以至少有3个数小于等于它。所以整个数组中至少有3*n*1/10=n*3/10个数小于等于最终的中位数。
将最终的中位数作为pivot,那么最坏情况下第k大数落在较大的那块中,接下来递归计算的复杂度是T(n*7/10)
cn表示对数组按pivot进行元素交换的复杂度
上式可以用代换法证明T(n)=O(n)
假设T(n)=kn,k为常数
则 T(n)<=T(n*1/5)+T(n*7/10)+cn=n*k/5+n*7*k/10+cn=(k/5+7/10*k+c)n
所以,T(n)=O(n)

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>