C++实现第K顺序统计量的求解方法


一个n个元素组成的集合中,第K个顺序统计量(Order Statistic)指的是该集合中第K小的元素,我们这里要讨论的是如何在线性时间(linear time)里找出一个数组的第K个顺序统计量。该问题的算法对于C++程序员来说有一定的借鉴价值。具体如下:

一、问题描述:

问题:给定一个含有n个元素的无序数组,找出第k小的元素。

k = 1 :最小值
k = n :最大值
k = ⌊(n+1)/2⌋ or ⌈(n+1)/2⌉ :中位数

找最大值或最小值很简单,只需要遍历一次数组并记录下最大值或最小值就可以了。我们在这里要解决的问题是一般性的选择问题。

一种原始的解决方案是,用堆排序或归并排序将输入数据进行排序,然后返回第k个元素。这样在Θ(nlgn)时间内一定可以解决。但是我们希望有更好的方案,最好是线性时间。

二、期望线性时间的解决方案:

为了在线性时间内解决这个选择问题,我们使用一个随机的分治算法,即RANDOMIZED-SELECT算法。此算法是使用随机化的快速排序中的随机划分子程序,对输入数组进行随机划分操作,然后判断第k小元素在划分后的哪个区域,对所在区域进行递归划分,最后找到第k小元素。

伪代码如下:

RANDOMIZED-SELECT(A,p,q,i) // i-th smallest in A[p..q] 
  if p = q 
    then return A[p] 
  r = RANDOMIZED-PARTITION(A, p, q) 
  k = r-p+1  // A[r] is k-th smallest 
  if i=k 
    then return A[r] 
  if i<k 
    then return RANDOMIZED-SELECT(A, p, r-1, i) 
  else 
    then return RANDOMIZED-SELECT(A, r+1, q, i-k) 

这里的RANDOMIZED-PARTITION()是随机版的划分操作(快速排序的分析与优化),可见本算法是一个随机算法,它的期望时间是Θ(n)(假设元素的值是不同的)。

1、Lucky-Case:最好的情况是在正中划分,划分的右边和右边的元素数量相等,但是1/10和9/10的划分也几乎一样好。可以这么说,任何常数比例的划分都和1/2:1/2的划分一样好。这里以1/10和9/10的划分为例,算法运行时间递归式为T(n) <= T(9n/10) + Θ(n),根据主定理得到T(n) <= Θ(n)。

2、Unlucky-Case:虽然主元的选取是随机的,但是如果你运气足够差,每次都得到0:n-1的划分,这就是最坏的情况。此时递归式为T(n) = T(n-1) + Θ(n),则时间复杂度为T(n) = Θ(n^2)。

3、Expected-Time:期望运行时间为Θ(n),即线性时间。这里就不证明了,证明需要用到指示器随机变量。

C++代码如下:

/************************************************************************* 
  > File Name: RandomizedSelect.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
#include<cstdlib> // srand rand 
using namespace std; 
 
void swap(int &a, int &b) 
{ 
  int tmp = a; 
  a = b; 
  b = tmp; 
} 
 
int Partition(int A[], int low, int high) 
{ 
  int pivot = A[low]; 
  int i = low; 
  for(int j=low+1; j<=high; ++j) 
  { 
    if(A[j] <= pivot) 
    { 
      ++i; 
      swap(A[i], A[j]); 
    } 
  } 
  swap(A[i], A[low]); 
  return i; 
} 
 
int Randomized_Partition(int A[], int low, int high) 
{ 
  srand(time(NULL)); 
  int i = rand() % (high+1); 
  swap(A[low], A[i]); 
  return Partition(A, low, high); 
} 
 
int Randomized_Select(int A[], int p, int q, int i) 
{ 
  if(p == q) 
    return A[p]; 
  int r = Randomized_Partition(A, p, q); 
  int k = r-p+1; 
  if(i == k) 
    return A[r]; 
  if(i < k) 
    return Randomized_Select(A, p, r-1, i); 
  else 
    return Randomized_Select(A, r+1, q, i-k); 
} 
 
/* 测试 */ 
int main() 
{ 
  int A[] = {6,10,13,5,8,3,2,11}; 
  int i = 7; 
  int result = Randomized_Select(A, 0, 7, i); 
  cout << "The " << i << "th smallest element is " << result << endl; 
  return 0; 
} 

三、最坏情况线性时间的解决方案

虽然最坏情况Θ(n2)出现的概率非常非常小,但是不代表它不会出现。这里就介绍一个非同一般的算法,以保证在最坏情况下也能达到线性时间。

这个SELECT算法的基本思想就是要保证对数组的划分是一个好的划分,它通过自己的方法选取主元(pivot),然后将pivot作为参数传递给快速排序的确定性划分操作PARTITION。

基本步骤:

①.将输入数组的n个元素划分为n/5(上取整)组,每组5个元素,且至多只有一个组有剩下的n%5个元素组成。

②.寻找每个组织中中位数。首先对每组中的元素(至多为5个)进行插入排序,然后从排序后的序列中选择出中位数。

③.对第2步中找出的n/5(上取整)个中位数,递归调用SELECT以找出其中位数x。(如果是偶数取下中位数)

④.调用PARTITION过程,按照中位数x对输入数组进行划分。确定中位数x的位置k。

⑤.如果i=k,则返回x。否则,如果i < k,则在地区间递归调用SELECT以找出第i小的元素,若干i > k,则在高区找第(i-k)个最小元素。

如下图所示:

                            

总结:

RANDOMIZED-SELECT和SELECT算法是基于比较的。我们知道,在比较模型中,排序时间不会优于Ω(nlgn)。之所以这里的选择算法达到了线性时间,是因为它们没有使用排序就解决了选择问题。另外,我们没有使用线性时间排序算法(计数排序/桶排序/基数排序),是因为它们要达到线性时间对输入有很高的要求,而这里不需要关于输入的任何假设。



相关阅读:
ThinkPHP基于PHPExcel导入Excel文件的方法
浅谈html中input只读属性readonly和disable的区别
Win7系统提示“Windows无法连接到无线网络”的错误信息的解决方法
PHP 使用redis简单示例分享
Ubuntu下VirtualBox的vdi文件克隆方法
C++的头文件和实现文件详解
ASP.NET中TimeSpan的用法实例解析
Win10 最新预览版10061已发放 暂不支持升级
Android编程之SurfaceView实例详解
PHP使用pear实现mail发送功能 windows环境下配置pear
用JS动态改变表单form里的action值属性的两种方法
PHP实现自动对图片进行滚动显示的方法
Android Camera开发手电筒功能
Win10 10122预览版 更新内容大全
快速导航
PHP MySQL HTML CSS JavaScript MSSQL AJAX .NET JSP Linux Mac ASP 服务器 SQL jQuery C# C++ java Android IOS oracle MongoDB SQLite wamp 交通频道 作文范文 甄嬛传经典台词大全 《白鹿原》读后感 对人生有启示的小故事 告别“摩尔庄园” XX年工作总结和XX年度工作思路(市政务中心)_工作总结范文 鸡首说 韩国旅游必备行前手册 化验室工作总结 街道司法所2013年工作计划 壮哉大阅兵作文500字 ★活着读后感1000字 我和你的距离有多远 初中初一作文600字:刺豚式防盗锁 读《保姆狗的阴谋》有感400字 仙人掌的魅力 如何做到信守承诺 在全区社区工作会议上的讲话 回 家 初中入团志愿书100字范文 如何让婚姻成长 父母的眼睛最美作文500字 教师参观永不磨灭的丰碑焦裕禄事迹展心得桧 孩子,你什么时候才能读懂爹娘的 心? 教师思想工作小结 未卜先知造句 北京笔记,暗物质、暗能量和反物质及其粒子的猜想(十一) 成长的烦恼_关于成长的烦恼作文1000字 学校政治学习心得体会 信管专业暑假实习报告 明月作文100字 2015年度质量管理工作计划 撕名牌活动策划 祖国在我心中作文:祖国,你在我心中 2014年初三学生入团申请书格式 女孩自我介绍作文600字 初心,为闪耀的红十字 情楼待友睹佳人[合欢带新韵] 关于小学教学年终工作总结范文 很后悔一件事情 贵州人的逃命夜 九月作文300字 经济协调办述职报告 初中初三作文800字:同桌的散文与他 人生不放弃——读《假如给我三天光明》有感作文700字 一个人的城,多少忧伤 我要当升旗手了 作文小实验300字 弄坏门的检讨书 一丝惬意心中来作文550字 刘强东在哈佛大学演讲全文

Copyright © 2016 phpStudy |