用O(nlgk)时间查找k分位数(所谓k分位数：将n个元素分成k个大小相等的集合的k-1个顺序统计量)
用O(nlgk)时间查找k分位数(所谓k分位数：将n个元素分成k个大小相等的集合的k-1个顺序统计量)
相关问题：
The kth quantiles of an n-element set are the k 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). Give an O.n lg k/-time algorithm to list
the kth quantiles of a set.
对一个含有n个元素的集合来说，所谓k分位数（the kth quantile），就是能把已排序的集合分成k个大小相等的集合的k-1个顺序统计量。给出一个能输出某一集合的这k-1个顺序统计量的O(nlgk)时间的算法。
思考过程：
开始我的想法是，既然是已排序的集合，那么我就写一个循环for(i=n/k;i<n;i+=n/k) cout<<A[i]<<" " n/k代表k个集合中的每个集合大小为n/k个元素。每隔n/k个元素就输出一个数，这样循环k-1次就输出了k-1和顺序统计量也就是k分位数。这样时间复杂度就是O(k)，显然比O(nlgk)小，但是题目又要求给出O(nlgk)的算法。我想这可能是翻译有误，”sorted“在这句话里翻译成“已排序”是否妥当？，如果改成原数组初始未排序。那么如果还按照刚才的算法，明显不能求出。然后我就想出另外一个超级简单的算法。利用书中9.3节给出的线性时间求第i小元素的函数SELECT。还是for(i=n/k;i<n;i+=n/k)循环里面循环调用SELECT函数求出第n/k,第2n/k,....第(n-1)n/k小元素不就求出了k分位数？但是仔细研究下其中的时间复杂度发现 O((k-1)n)明显要比O(nlgk)大，所以此算法不可取。
最后正确的算法是利用类似二分法进行查找选择。为什么说是类似二分法呢？ 因为传统的二分法是一直取一半进行划分，而这里的近似二分法是k=偶数时，当然就是原来的二分法。而k=奇数时，选择近似二分法，就是选取k/2附近的整数进行划分。比如k=7，那么k/2=3.5 所以递归的低区就是k=3等分，高区就是k=4等分。这样可以看成一颗递归树，从根到叶子是一个不断递归找k等分直到到叶子这一层找到全部的k-1个顺序统计量为止。次递归树的高度是2^h=k => h=lgk.而树的每层都经过了最多O(n)时间的SELECT函数的查找，所以总的时间就是O(nlgk)。
代码如下：
#include <iostream>
#include <time.h>
using namespace std;
const n=16;//想取多少个元素可自己调整。
int t;
//创建一个装有数组A以每5个元素为1组共n/5组，每组的中位数放入到数组B中，组成一组含有n/5个中位数的数组B
int Find(int A[n],int p,int r);//递归当前数组A中从p到r个元素，以找到辅助中位数数组B的中位数。
int PARTITION(int A[],int p,int r,int t)//t代表中位数数组B中的中位数，这里t代表为主元。
{
int i=p-1,k=0;
for (int j=p;j<=r;j++)
{
if (A[j]<t)//将比主元t大的元素交换到数组A的右边去，比主元t小的到数组A的左边。
{
i++;
swap(A[i],A[j]);
}
if (A[j]==t)//如果A[j]等于主元
{
k=j;//那么记录下主元在A中的位置。
}
}
swap(A[i+1],A[k]);//完成划分操作，主元左边的元素都小于主元，主元右边的元素都大于主元。
return i+1;
}
int SELECT(int A[],int p,int r,int i)//i表示第i小的数。
{
if (p>=r)
{
return A[p];
}
int t=Find(A,p,r);//返回的t代表辅助数组B的中位数。
int q=PARTITION(A,p,r,t);
int k=q-p+1;
if (i==k)
{
return A[q];
}
else if(i<k)
{
return SELECT(A,p,q-1,i);
}
else return SELECT(A,q+1,r,i-k);
}
int Find(int A[n],int p,int r)
{
int key=0,t=0,m=r-p+1,h=0;
if (m%5==0)//如果当前数组A的大小能被5整除，那么这以5个元素为一组的m/5组数，没有余数那一组
{
h=m/5;
}
else//否则，应该加上含有余数的那一组。
{
h=m/5+1;
}
int *B=new int[h];
for(int j=0;j<h;j++)
{
B[j]=0;
}
for (int k=0;k<h;k++)//5个数一组，共h组。进行插入排序。
{//经过最多h=n/5+1次循环，那么总共循环了25h=25(n/5+1)=5n+25=O(n)次
for (int j=t+1+p;j<=5+t+p&&j!=r+2;j++)//h组中每组进行插入排序。注意加上数组初始坐标p(当前数组A的初值坐标)+t(在p基础上每5个为1组)
{//运行时间分析：5个一组运行插入排序，每次插入排序需要的时间是O(n^2)=5^2=25是基于固定划分的固定常数
key=A[j-1];
int i=j-1;
while (i>t+p&&A[i-1]<key)
{
A[i]=A[i-1];
i=i-1;
}
A[i]=key;
}
t+=5;//进入下一个5个元素为一组的插入排序
}
k=0;
for (int i=0;i<h&&k<h;i++)//经过最多h=n/5+1次循环(O(n))，将当前数组A中的每组的中位数依次放入到B中
{
if (i<h-1)
{
B[k]=A[2+5*i+p];
k++;
continue;
}
if(m%5!=0)
{
B[k]=A[5*i+p+(m%5)/2];
}
else
{
B[k]=A[2+5*i+p];
k++;
}
}
if (h==1)
{
return B[0];//当辅助数组B只剩下一个数时，那么这个数就是中位数的中位数。
}
else
{
return SELECT(B,0,h-1,(h-1)/2+1);//如果数组B元素个数是偶数，那么取数组B中的较小值。
}
}
void The_kth_quantile(int A[],int B[],int p,int r,int k)//k代表要分成多少元素个数相等的集合。
{
static j=0;
if (r-p+1>t)//这k个集合中每个集合有n/k个元素。
{
if (k%2!=0)//奇等分时。
{
int i=((r-p+1)/k)*((k-1)/2);//对当前数组进行近似二分法，例如k=5 2:3 i=2n/5 n=r-p+1
int h=SELECT(A,p,r,i);//第i小元素就是数组中A[i-1]
B[j]=h;j++;
The_kth_quantile(A,B,p,i-1+p,(k-1)/2);
The_kth_quantile(A,B,i+p,r,(k+1)/2);
}
else//偶等分时。
{
int i=((r-p+1)/k)*(k/2);//对当前数组进行二分法
int h=SELECT(A,p,r,i);
B[j]=h;j++;
The_kth_quantile(A,B,p,i-1+p,k/2);
The_kth_quantile(A,B,i+p,r,k/2);
}
}
}
void main()
{
int k=0;
int A[n]={0};
//随机输入数组
srand( (unsigned)time( NULL ) );
cout<<"原数组："<<endl;
for (int i=0;i<n;i++)
{
A[i]=rand()%100;
cout<<A[i]<<"\t";
}
cout<<endl;
cout<<"请输入需要划分的k等份=";
cin>>k;
cout<<endl;
int*B=new int[k+1];
for (i=0;i<k+1;i++)
{
B[i]=0;
}
t=n/k;
if (n%k)
{
cout<<"不存在k分位数！"<<endl;
}
else
{
The_kth_quantile(A,B,0,n-1,k);
}
for (i=0;i<k-1;i++)
{
cout<<B[i]<<" ";
}
cout<<endl;
}
评论暂时关闭