计数查找算法的研究网(2)
2013-05-25 01:13
导读：该算法得时间复杂度为O(6.09*N) [5] ，与Count-Search算法相比较可知：Count-Search算法具有更好的时间复杂度。 4 算法测试与比较 为了证实上述结论，在ACER Tra
该算法得时间复杂度为O(6.09*N)
[5]，与Count-Search算法相比较可知：Count-Search算法具有更好的时间复杂度。
4 算法测试与比较
为了证实上述结论，在ACER TravelMate 2420 (PM730，512M内存，80G硬盘)，Windows XP 平台上编写了三种查找算法的子程序，进行了相应的实验测定，其结果如表1 所示。（实验数据全部采用均分布的无符号整型随机数）
表1
注：以上时间单位为毫秒MS。
根据以上数据我们可以绘制出数据规模和时间的函数图像。
观察分析以上实验结果，可以看出：基于快速排序的查找算法和其他算法相比较具有较差的效率；而采用了分治策略的Divide- Select查找算法的效率可以是基于快速排序的查找算法的几十倍，其时间复杂度在图中也反映为线性。而基于计数排序的查找算法（Count-Search）的时间复杂度同样达到了线性，但是效率却比Divide-Select更高，通过上述实验可以得知：在进行无符号整数查找时，基于计数排序的查找算法（Count-Search）在时间上是最优的。
5 Count-Search的应用范围
在查找无符号整数集合时，应用Count-Search算法，能够降低查找时间复杂度。但是应用Count-Search算法时要注意：该算法只适用于整数的查找，且查找集合S的最大值M与S中元素个数N不成指数关系，即M不能远大于N。因为当M过大时，首先内存开销就会很大，其次时间复杂度也会相应的提高。
该算法充分的运用了整数的特性，整个运算过程中无需数据的比较和交换，大大降低了算法的时间复杂度，因此该算法可以在工程统计中得到大规模运用。例如：随着的和应用，网络中的信息量成倍的扩大，而在其中我们关注的最多的则是统计排名比较靠前的信息，如果将全部过亿的统计量排序，则由于数据量过大，则会浪费大量的时间和资源。而采用Count-Search的查找算法，就可在线性的时间完成。
6 结束语
本文中提出的一种基于计数排序算法的整数查找算法，该算法在运算过程中无需进行数据的比较和交换，该算法可以应用到大规模的整数查找，算法的时间复杂度很低，而且避免的大量的数据比较和交换，同时在时间上是最优的。
[1]崔泽鹏，李伟生. EREW PRAM模型上指数级分割待处理数据集的并行多选算法[J].北方大学学报，2003，(2)：46-49
[2]班志杰，高光来. 一种Byte查找第K个元素的算法研究[J].
内蒙古大学学报，2004，(3)：322-324
[3]Thomas H.Cormen Charles E.Leiserson. 《算法导论》[M]. 北京：机械出版社。2006.9：98-99
[4]Muhammad H.Alsuwaiyel. An optimal parallel algorithm for the multiselection problem[J]. Parallel Computing，2001，(27)：861—865
[5]江华. 求第K个元素的快速排序算法[J]. 韶关学院报，2003，(6)：32-34
[6]王晓东.《算法设计与分析》[M] .北京：
清华大学出版社，2003.1：39-43
