计数查找算法的研究

上传者：网友
|

翻新时间：2013-12-18

收藏到账号

全屏

计数查找算法的研究

摘要查找第K大的元素的问题在机查找计数中占有很重要的地位。若直接进行排序，则算法平均时间复杂度为O(N*Lg(N))。

但是比较好的策略有求第K大的元素的经典算法——基于分治思想的Divide-Select [1][6]，算法的时间复杂度为O(6.09*N ) [5]。由于基于比较的排序算法在最坏的情况之下，都需要进行N*Lg(N)次比较[3]，故本文提出了一种基于非比较算法的无符号整数查找算法——Count-Search（计数查找算法）。

该算法应用于无符号整数的查找，算法的平均时间复杂度为O( 2*N ) 。关键字非比较；查找；排序；时间复杂度；计数；整数

2.3 时间复杂度分析程序2-3行时间复杂度为O(N)，第4-8行时间复杂度为O(M)，该算法的时间复杂度为T(n)= O( N+M)。如果数组A[]的最大值M与N成线形关系，即M=O(n)，则其时间复杂度为T(n) = O( 2N)。

3 Count-Search算法与Divide-Select算法的比较注：以上时间单位为毫秒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，

7)：861—865[5]江华. 求第K个元素的快速排序算法[J]. 韶关学院报，2003，

(6)：32-34[6]王晓东.《算法设计与分析》[M] .北京：清华大学出版社，2003.1：39-43