计数查找算法的研究.doc

计数查找算法的研究 摘  要  查找第K大的元素的问题在机查找计数中占有很重要的地位。若直接进行排序，则算法平均时间复杂度为O(N*Lg(N)。但是比较好的策略有求第K大的元素的经典算法基于分治思想的Divide-Select 16，算法的时间复杂度为O(6.09*N ) 5。由于基于比较的排序算法在最坏的情况之下，都需要进行N*Lg(N)次比较3，故本文提出了一种基于非比较算法的无符号整数查找算法Count-Search（计数查找算法）。该算法应用于无符号整数的查找，算法的平均时间复杂度为O( 2*N ) 。     关键字 非比较；查找；排序；时间复杂度；计数；整数 1  算法的基本思想    通常的排序算法在空间和时间复杂度一定的情况下的时间开销主要是关键字之间的比较和记录的移动。基于计数排序的查找算法（Count-Search）的实现在整个过程无需进行数据的比较，算法的时间复杂度为O( 2*N )。该算法的基本原理是：    根据无符号整数的大小可以和数组元素的下标对应的原则，在程序中可以用整数数组来储存元素的大小关系。对于一个大小为N的整型数组a，对于每一个元素x，用数组中的元素ax记录下小于等于它的元素个数，当要找的是集合中第K个大的元素时，则只需找到该数组中第N-K+1小的元素。即只需要找到该数组中第一个大于或等于 N-K+1的元素，该元素的下标即为第K大的数。    该算法具体可以描述为：假设n个输入元素的每一个都是介于0到M之间的整数，此处M为某个无符号整数。    (1) 对于每一个输入的元素X，首先确定出等于X的元素个数。    (2) 对于每一个元素X，确定小于等于X的元素个数。    (3) 从数组首地址出发顺序查找到第一个小于等于K的元素，则该元素X即为所要查找的第K小的数，顺序查找到第一个小于等于N-K+1的元素，则该元素X即为所要查找的第K大的数。2  计数查找算法的C语言实现(CountSearch)2.1 数据结构的设计与程序    假定输入的数组为整型数组A1.N，lengthA=N，数组中元素最大值为M，数组C记录整数元素的大小关系。Count-Search(int* A，int K)memest(C，0)/C0.M=0初始化Cfor j=1 to lengthAdo CAj=CAj+1/Ci包含等于i的元素个数for i=1 to Mbegindo Ci = Ci+Ci-1  /Ci包含小于等于i的元素个数if( Ci>= N-K+1 )   break；/寻找到第N-K+1的元素，即为第K大的元素end 2.2  算法步骤分析     第一步：第一行的初始化操作之后，在2-3行检查每一个输入元素。如果一个输入元素的值为i，即Ci的值加1 。于是在第3行之后，Ci中存放了等于i的元素个数（整数i=0，1，M）。    第二步：在第4-8之后，Ci存放了小于等于i的元素的个数。最后从数组C的首地址出发顺序查找第一个使得Ci>=N-K+1的元素，则第K大的元素即为i 。    下图给出了Count-Search的运算过程：图1表示初始数组A，C。图2表示运行完程序2-3行，数组C中的元素Ci存放的是数组A中等于i的元素个数。图3表示运行4-8行的结果，C中元素Ci存放的是数组A中小于等于i的元素个数。例如查找该数组第3大的数，则由于C2=4>=3，故元素2即为所要查找的第3大的数。 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算法的比较    Divide-Select 的基本思想是：通过在线性的时间内找到一个划分基准，使得按这个基准所划分出的两个子数组的长度都至少为原数组的倍（0<<1是某个正常数），然后对子数组递归的调用Divide-Select算法，这样就可以在线性的时间内完成查找任务。6