博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
《算法导论》学习总结 — 9.第九章 中位数和顺序统计学
阅读量:5846 次
发布时间:2019-06-18

本文共 2026 字,大约阅读时间需要 6 分钟。

这一章的内容很简单,基本都是一些概念。

:在一个由n个元素组成的集合中,第i个顺序统计量(order statistic)是该集合中第i小的元素。

最小值是第1个顺序统计量(i=1)

最大值是第n个顺序统计量(i=n)

中位数:一个中位数(median)是它所在集合的“中点元素”,当n为奇数时,i=(n+1)/2,当n为偶数是,中位数总是出现在 (下中位数)和 (上中位数)。

找最大值/最小值问题,通过比较n-1次可以得出结果。

MINIMUM(A)1  min ← A[1]2  for i ← 2 to length[A]3         do if min > A[i]4                then min ← A[i]5  return min

如果要同时找出最大值和最小值,则比较次数最少并不是2*n-2,而是 ,我们可以将一对元素比较,然后把较大者于max比较,较小者与min比较,这样就只需要 。

如果是一般的选择问题,即找出一段序列第i小的数,看起来要比找最大值或最小值要麻烦,其实两种问题的渐进时间都是 。

首先看看这个强悍的伪代码:

RANDOMIZED-SELECT(A, p, r, i)1  if p = r2      then return A[p]3  q ← RANDOMIZED-PARTITION(A, p, r)4  k ← q - p + 15  if i = k          ▹ the pivot value is the answer6      then return A[q]7  elseif i < k8      then return RANDOMIZED-SELECT(A, p, q - 1, i)9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

这个算法利用了随机化的Partition算法,这个实在第七章的随机化快排中讲到:,不记得的可以先复习下前面的快排。

这个随机化的选择算法返回数组A[p..r]中第i小的元素。

具体实现如下:

/*Author: Tanky WooBlog:   www.WuTianQi.comAbout:  《算法导论》第9章 查找序列第i小的数字*/#include #include using namespace std;int Partition(int *arr, int beg, int end){	int sentinel = arr[end];	int i = beg-1;	for(int j=beg; j<=end-1; ++j)	{		if(arr[j] <= sentinel)		{			i++;			swap(arr[i], arr[j]);		}	}	swap(arr[i+1], arr[end]);	return i+1;}int RandomPartition(int *arr, int beg, int end){	int i = beg + rand() % (end-beg+1);	swap(arr[i], arr[end]);	return Partition(arr, beg, end);}int RandomSelect(int *a, int p, int r, int i){	if(p == r)		return a[p];	int q = Partition(a, p, r);	int k = q-p+1;	if(i == k)		return a[q];	else if(i < k)		return RandomSelect(a, p, q-1, i);	else		return RandomSelect(a, q+1, r, i-k);}int main(){    int a[] = {0, 89, 100, 21, 5, 2, 8, 33, 27, 63};    int num = 9;    int ith;	cout << "序列为: ";    for(int i=1; i<=num; ++i)        cout << a[i] << " ";	cout << endl;    ith = RandomSelect(a, 1, num, 2);	cout << "序列中第2小的数字是: " << ith << endl;	getchar();    return 0;}

结果如图:

在(89, 100, 21, 5, 2, 8, 33, 27, 63)中查找第二小的数字是5. 

该算法的平均情况性能较好,并且又是随机化的,所有没有哪一种特别的输入会导致最坏情况发生。

转载于:https://www.cnblogs.com/downtjs/p/3357937.html

你可能感兴趣的文章
在网上看到的机房布线图片
查看>>
用treeset对字符串进行长度排序
查看>>
sql(SqlServer)编程基本语法
查看>>
linux 文件特殊权限
查看>>
ln -s 软链接应用-磁盘空间不够用的解决方案
查看>>
Windows7操作系统安装教程(图文)
查看>>
我的友情链接
查看>>
ASA 同端口级别如何互访
查看>>
net发送apns解决方案(iphone push)
查看>>
tomcat性能调优
查看>>
springmvc 不指定访问路径后缀都会匹配的
查看>>
Ubantu权限设置
查看>>
基于web的文件管理/目录结构展示(ufinder、elfinder)……的心路历程
查看>>
Linux下使用parted分区工具为大于2T硬盘分区
查看>>
Ubuntu下口袋妖怪终端主题安装
查看>>
重装GRUB
查看>>
cookie 和session 的区别详解
查看>>
windows编译hadoop 2.x Hadoop-eclipse-plugin插件
查看>>
我的友情链接
查看>>
[软件开发必备]计算机基础知识
查看>>