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 服务器 CMS SQL jQuery C# C++ java Android IOS oracle MongoDB PostgreSQL SQLite 交通频道 曲阜-张家口 喀什-淮安 安顺-合肥 淮北-滕州 吕梁-乳山 北京-龙口 黄石-上虞 哈尔滨-临沂 新余-崇明 寿光-锡林浩特 盐城-大丰 保定-鄂尔多斯 亳州-招远 海盐-新余 云浮-怒江 遂宁-永州 宣城-十堰 安顺-聊城 石嘴山-安康 三明-南安 阿克苏-丹东 阿坝-邯郸 金华-牡丹江 诸城-普洱 济宁-益阳 郑州-石嘴山 石河子-新乡 肇庆-普兰店 山南-菏泽 榆林-宜都 安康-荣成 绥化-七台河 鹤岗-昌都 益阳-德宏 吉安-丹东 东莞-温州 营口-恩施 新昌-通辽 靖江-昌吉 海城-宝鸡 昆山-北京 和田-鹤壁 石河子-大丰 镇江-文山 台州-海安 洛阳-诸暨 防城港-莱芜 宿州-朔州 如东-乌兰浩特 九江-白山 南通-济南 淄博-邹平 辽阳-恩施 荆门-青州 大庆-宁波 贺州-瑞安 昆明-大庆 太原-济宁 绥化-阿坝 孝感-通化 海南-安顺 朝阳-菏泽 河池-莆田 吉林-盐城 芜湖-蓟县 龙海-洛阳 南平-温州 扬州-兖州 大连-溧阳 温岭-秦皇岛 六安-深圳 招远-奉化 大庆-邵阳 普洱-广安 汉中-青州 天门-徐州 增城-湖州 宁海-周口 寿光-黄冈 银川-晋中 松江南-长沙南 东乡-勉县 晋州-泰山 滕州-吐哈 冷水江东-怀化 醴陵东-萍乡北 汉源-绵阳 江宁西-武义北 广州东-成都 南陵-济南西 五叉沟-乌兰浩特 高碑店-南宁 兴安北-嘉兴南 保定东-许昌东 南昌-宣城 镇赉-扎赉诺尔西 寒葱沟-铁岭 眉山-燕岗 山阴-晋州 佳木斯-青州市 义乌-武穴 太平川-吴桥 石家庄-公主岭 浠水-唐河 柳州-张家界 泰山-分宜 小白-长春 长春-福泉 汉阴-天津 石林-田林 甘谷-和硕 镇赉-集宁南 昌图-瓦拉干 包头-绥德 南京-迁安 郯城-沂南 东坡-南陈铺 潮州-肇庆 角美-惠东 麻山-西麻山 绥中-西平 宣家沟-四家子 三门峡西-武威南 古镇-顺德 邢台-南阳 沙日乃-达日其嘎 叶柏寿-赤峰东 庆丰-宝龙山 阳泉北-石家庄 衡水-吉安 天水-灵石 邵阳-丰城 晋州-宿州 永州-潢川 缙云-哈尔滨 正镶白旗-化德 武昌-武当山 营口东-滨海 桂林北-秦皇岛 哈尔滨-随州 绍兴北-凯里南 西大庙-统军庄 益阳-月山 邹城-吴桥 深圳西-新化 龙游-简阳 茄子溪-长河碥 茄子溪-古家沱 泰来-镇安 义乌-自贡 永康-菏泽 聊城-渠县 公主岭-汉口 定西-邵阳 天津西-南京 三明北-瑞安 嵯岗-大虎山 内江-安康 天门南-巴东 涪陵-樟树

Copyright © 2016 phpStudy |