现在的位置: 首页 > 综合 > 正文

众数问题分析

2013年03月31日 ⁄ 综合 ⁄ 共 3140字 ⁄ 字号 评论关闭

问题描述
•给定一个数组,找出其中出现次数最多的那个元素(即众数)。

核心思想
•普遍的解决思路。
•如果我们将所有元素的出现次数进行统计,并从中找出次数中的最大值,那么,这个最大值对应的元素就是众数。
•从这一思想出发,我总结出以下两种算法
–算法1:利用排序算法统计
–算法2:利用数组或散列表统计

算法1
•算法思路:首先将数组元素按照大小排序,然后按顺序扫描一遍数组,扫描的同时进行统计。这样,通过一次排序和一遍扫描,我们就能够找到众数。
•关键步骤:排序,扫描统计

算法代价分析
1、时间代价
•由于扫描的时间代价是Θ(n)的,所以算法的总时间代价主要依赖于排序算法的代价。
•如果我们选取Θ(nlgn)的排序算法,最终的时间代价是Θ(nlgn)+Θ(n)= Θ(nlgn)
•Θ(nlgn)是基于比较的排序不可逾越的时间下界,也是该算法能够达到的最低代价。

2、空间代价
•扫描统计时,我们只需要三个辅助变量:一个用于计数,一个用于记录当前出现次数最多的元素的出现次数,一个用于记录当前出现次数最多的元素。
•所以,如果排序算法的辅助空间是O(1)的,那么整个算法的辅助空间代价就是O(1)的。

改进想法
•思想:改进排序算法,使得排序算法在排序的同时就统计出现次数,并记录次数最多的元素,以及删除所有重复的元素。这样,不仅可以减小排序的规模,并且省去了最后扫描的步骤,在一定程度上优化了该算法。
•然而,虽然改进后的算法比原始算法效率高,但是由于其本质仍然是基于比较的排序算法,所以时间代价还是Θ(nlgn)的,并没有在数量级上取得突破。

算法2
•算法思路:直接统计各元素出现的次数,用某一种线性数据结构存储统计结果。
•朴素的实现方法:用一个辅助数组存储统计结果,统计时用数组下标对应相应元素。

算法代价分析
1、时间代价
•用下标对应元素,访问时间O(1)。顺序扫描一遍原数组,就可以得到统计结果。
•总的时间代价Θ(n)。
算法代价分析
2、空间代价
•依赖于原数组中元素的范围。
•假设我们知道元素集中分布在宽度为m的区间内,那么我们就可以开辟大小为m的数组用于统计。这时,最后使用的辅助空间便是O(m)的。
•然而我们一般并不能确切地知道数组中数的范围,或者数组中元素的分布非常稀疏(即数组中有相当比例的空间存储的统计数为0)。这时,下标连续分布的、上下界明确的数组就难以承担其职责了。
•因此,我们必须改进数据结构,以更加广泛地适应算法的需求。

改进想法
•核心思想:采用散列表。
•散列表的优点:存储灵活,检索效率高。
•因此,使用散列表能够有效地替代数组,实现算法的功能。
•散列表的缺点:空间利用率低。
•据实验,当散列表的负载因子小于0.5时,散列表在大部分情况下的检索长度小于2。但是,如果超过0.5,散列表的性能就会急剧下降。
•因此,如果原数组元素分布稠密,使用散列表的空间效率就要低于使用数组。
改进后算法的代价分析
•前提假设:散列表的性能良好(负载因子小于0.5)

1、时间代价
•同样是扫描一遍,然而每一次的平均探查长度大于1。因此,时间效率要比数组低。
•但是,由于散列表性能良好,平均探查长度小于2,所以时间代价依然是O(n)的。
改进后算法的代价分析
2、空间代价
•如果原数组中共有m个不同的元素,那么,由于负载因子小于0.5,因此散列表的大小至少是2m。空间效率低于元素稠密时的数组,但是可能会远高于数据稀疏时的数组。

算法比较
•这份报告中主要介绍了两种算法思想。他们各有利弊,对比如下:
1、基于排序的算法
•时间代价:Θ(nlgn)
•空间代价:O(1)
2、直接统计的算法
•时间代价:Θ(n)
•空间代价:Ω(m)
•从以上对比,我们可以看出:算法2是利用空间换时间,虽然使用了大量的辅助空间,但是时间代价要远低于算法1。
•我们的算法设计,就是一个权衡利弊的过程。很多时候,时间和空间不可兼得,那么,我们就要根据用户的需求选择合适的算法,以实现时间更快或者空间更省。
•而对于算法2,我们同样面临着选择:使用数组还是使用散列表。这一选择基于数组元素的分布:如果数组元素分布稠密,使用数组自然是又快又省;可是,如果分布稀疏或是不确定,散列表的灵活性就派上了用场。
•因此,除了用户需求,我们面对的数据本身也左右着我们的选择。
•在实际应用中,众数问题一般用于对大量数据的统计。
•下面举一些实例,来探讨实际问题中众数问题的解决方案。
实例1
•选票统计
•data*+=,“张三”,“李四”,“李四”,“张三”,“李四”,“李四”,“弃权”,“李四”,“张三”,“李四”,“张三”,“弃权”,“张三”……-
•数据规模大,数据范围有限,显然用数组更为方便。
实例2
•在一些科学实验中,我们要对实验数据进行统计和分析,这时众数只是我们研究的一部分,还有其他方面(例如分布情况)需要研究。这时,我们希望一次运算得到的信息量更多。
•这时我们也需要用数组。
010203040506070809010~2020~3030~4040~50数据:23.1,14.6,39.7,32.0,12.2……
范围
10~20
20~30
30~40
40~50
分布数
20
28
90
21
实例3
•假设1:有海量的数据需要统计,如果要排序只能通过外排序。
•假设2:硬盘空间足够用(操作过程中不必考虑空间开销)
•这时有一个用户需求,要得到这些数据的众数。
•如果用排序,我们必须考虑外排序可怕的时间代价。
•如果用数组或散列表,虽然会占用额外的硬盘存储空间。但是,如果这些数据需要经常增删,并且需要经常调用取众数操作,那么,保存这些统计结果将带来极大的方便。
总结
•解决众数问题主要有两种算法思想,其中算法2可以使用两种不同的辅助数据结构。这三者本身都是解决众数问题的很好的办法,他们之间并无优劣。具体实现时,我们选择哪种方法,要依赖于我们对时空的权衡,以及数据本身的性质。
•众数问题虽然很简单,但是从中折射出的关于时空权衡的考虑,是算法设计时会普遍遇到的问题,值得大家讨论和思考。

//众数问题
/*
问题描述:
给定含有n个元素的多重集合S,每个元素在S中出现的次数成为该元素的重数。多重
集S中重数最大的元素称为众数。
例如, S = {1,2,2,2,3,5}。
多重集s的众数是2,其重数为3。
编程任务:
对于给定的由n个自然数组成的多重集S,编程计算S的众数及其重数。
*/
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <map>

using namespace std;

int main()
{
	ifstream input("input.txt",ios::in);
	ofstream output("output.txt",ios::out);

	if (!input)
	{
		cerr<<"inputfile could not be opened"<<endl;
		exit(1);
	}

	map<int,int> number_count;

	int number;
	while(input >>number)
	{
		++number_count[number];
	}

	map<int,int>::iterator map_it  = number_count.begin();

	map_it++;
	int key = map_it->first;
	int maxcount = map_it->second;
	while(map_it != number_count.end())
	{
		if (maxcount < map_it->second)
		{
			maxcount = map_it->second;
			key = map_it->first;
		}
		++map_it;
	}
	output<<key<<endl<<maxcount;
	return 0;
}

抱歉!评论已关闭.