鸿 网 互 联 www.68idc.cn

算法导论之七(中位数和顺序统计量之选择算法)

来源:互联网 作者:佚名 时间:2014-12-31 07:38
本文阐述了如何使用期望和线性时间的选择算法求得第i顺序统计量,欢迎拍砖!

        实际生活中,我们经常会遇到这类问题:在一个集合,谁是最大的元素?谁是最小的元素?或者谁是第二小的元素?。。。。等等。那么如何在较短的时间内解决这类问题,就是本文要阐述的。

        先来熟悉几个概念:

        1、顺序计量

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

        2、中位数

        一个中位数是它所属集合的“中点元素”,当n为奇数时,中位数是唯一的,位于i=(n+1)/2处;当n为偶数时,存在两个中位数,分别位于i=n/2和i=n/2+1处。


一、最大值最小值问题

        直观的看,对于一个包含n个元素的集合中,要求其中最小的元素,需要做多少次比较呢?很容易想到,至少要做n-1次比较;我们只需要遍历集合来进行比较,每次记录较小的元素,遍历结束的时候即可得到最小的元素。对于最大值也可以这样求。

        如果问题是需要同时找到最大值和最小值呢,当然可以进行两次遍历,做2*(n-1)次比较,就可以得到最大值和最小值。但这并不是最优的,因为我们并不需要每个数既与最大值进行比较又与最小值进行比较。

        以偶数个元素的集合为例,我们可以先比较一下前两个元素,大的那一个先设为max,而小的那一个先设为min,而之后的元素由于是偶数个,所以拆成两个一组,先在组内进行一次比较,然后再将组内大的去与max比较,如果比max大,则替换max的值,否则不变;组内小的去与min比较,类似的操作直到遍历完整个元集合。那么一共进行的比较次数为:1+(n/2-1)*3=3n/2-2次。如果是奇数个元素的集合的话,省略第一次的比较操作,然后直接将max和min都设为第一个元素即可,后面的操作与偶数的情况相同。那么对于奇数个元素的集合而言,一共要进行的比较次数为:((n-1)/2)*3次。如果不考虑奇数还是偶数,我们至多需要进行3[n/2](不大于n/2的最大整数)次比较即可得到最大值和最小值,也即算法的时间复杂度为O(n)。


实现的代码也比较简单:

#include <iostream> typedef int T; using namespace std; /* * 包含结果的结构体,里面含有最大值和最小值 */ struct result { public: T max; T min; result() : max(0), min(0) { } }; result* getMinMax(int a[], int len); int main() { T a[9] = { 5, 8, 0, -89, 9, 22, -1, -31, 98 }; result* r1 = getMinMax(a, 9); cout << "最大值为:" << r1->max << ",最小值为:" << r1->min << endl; T b[10] = { 5, 8, 0, -89, 9, 22, -1, -31, 98, 2222 }; result* r2 = getMinMax(b, 10); cout << "最大值为:" << r2->max << ",最小值为:" << r2->min << endl; delete r1; delete r1; return 0; } result* getMinMax(T a[], int len) { result* re = new result(); if (len == 0) { return 0; } if (len == 1) { re->max = a[0]; re->min = a[0]; return re; } if (len == 2) { re->max = a[0] > a[1] ? a[0] : a[1]; re->min = a[0] < a[1] ? a[0] : a[1]; return re; } int max, min; int i = 0; if (len % 2 == 0) { //元素个数为偶数的情况 re->max = a[i] > a[i + 1] ? a[i] : a[i + 1]; re->min = a[i] < a[i + 1] ? a[i] : a[i + 1]; i += 2; } else { //元素个数为奇数的情况 re->max = a[i]; re->min = a[i]; i++; } while (i < len) { //在成对的数中比较取值,然后再分别与max和min进行比较 max = a[i] > a[i + 1] ? a[i] : a[i + 1]; min = a[i] < a[i + 1] ? a[i] : a[i + 1]; i += 2; re->max = re->max > max ? re->max : max; re->min = re->min < min ? re->min : min; } return re; }

二、求一个集合中第i小的元素,也即第i个顺位统计量

        看起来感觉好像要比求最大值和最小值要复杂许多,而实际上,求一个互异元素的集合中的第i小的元素,时间复杂度与上面的一样,也是O(n)。下面关于快速排序的知识,可以参看:算法导论之一(快速排序)

        这里要采用的思路与快速排序有些类似,快速排序找找到一个mid位置之后,要继续对mid两边的数组进行快速递归排序。而这里由于只需要找到第i个顺位统计量的位置,所以这个元素要么位于mid位置,要么位于mid左边的数组,要么位于mid右边的数组,所以只需要考虑一边即可。而对应到算法复杂度上,快速排序的期望时间复杂度为O(nlgn),而这里为O(n)。

        具体思路:

        1、采用快速排序的分组方式,但是稍加改进,每次分组的时候的key值不再是一个确定的位置的值,而是先从所有元素中随机挑选一个作为key值,,然后再将其与末尾的元素交换。这样的好处在于能够有效避免每次分组都是极度不平衡的状态:0:n-1。(从概率上看,随机选择key值则使得不存在一种固定的情况让最坏的情况每次都发生)。

        2、在得到随机分组结果之后,我们先看看得到的那个mid位置的元素与我们要找的第i顺位统计量是不是一个位置,如果是,则直接返回mid位置的元素。如果发现mid位置位于第i顺位统计量之前,则我们只需要递归的对分组的后面的那部分集合进行上面的操作即可,反之,如果发现mid位于第i顺位统计量之后,则我们只需要递归的堆分组的前半部分集合进行上面的操作即可。


代码如下:

上一篇:觉悟吧,少年!
下一篇:orangleliu 笔记本
网友评论
<