- 相關(guān)推薦
計數查找算法的研究
摘 要 查找第K大的元素的問(wèn)題在機查找計數中占有很重要的地位。若直接進(jìn)行排序，則算法平均時(shí)間復雜度為O(N*Lg(N))。但是比較好的策略有求第K大的元素的經(jīng)典算法——基于分治思想的Divide-Select [1][6]，算法的時(shí)間復雜度為O(6.09*N ) [5]。由于基于比較的排序算法在最壞的情況之下，都需要進(jìn)行N*Lg(N)次比較[3]，故本文提出了一種基于非比較算法的無(wú)符號整數查找算法——Count-Search（計數查找算法）。該算法應用于無(wú)符號整數的查找，算法的平均時(shí)間復雜度為O( 2*N ) 。 關(guān)鍵字 非比較；查找；排序；時(shí)間復雜度；計數；整數1 算法的基本思想
通常的排序算法在空間和時(shí)間復雜度一定的情況下的時(shí)間開(kāi)銷(xiāo)主要是關(guān)鍵字之間的比較和記錄的移動(dòng)�；谟嫈蹬判虻牟檎宜惴ǎ–ount-Search）的實(shí)現在整個(gè)過(guò)程無(wú)需進(jìn)行數據的比較，算法的時(shí)間復雜度為O( 2*N )。該算法的基本原理是： 根據無(wú)符號整數的大小可以和數組元素的下標對應的原則，在程序中可以用整數數組來(lái)儲存元素的大小關(guān)系。對于一個(gè)大小為N的整型數組a[]，對于每一個(gè)元素x，用數組中的元素a[x]記錄下小于等于它的元素個(gè)數，當要找的是集合中第K個(gè)大的元素時(shí)，則只需找到該數組中第N-K+1小的元素。即只需要找到該數組中第一個(gè)大于或等于 N-K+1的元素，該元素的下標即為第K大的數。 該算法具體可以描述為：假設n個(gè)輸入元素的每一個(gè)都是介于0到M之間的整數，此處M為某個(gè)無(wú)符號整數。 (1) 對于每一個(gè)輸入的元素X，首先確定出等于X的元素個(gè)數。 (2) 對于每一個(gè)元素X，確定小于等于X的元素個(gè)數。 (3) 從數組首地址出發(fā)順序查找到第一個(gè)小于等于K的元素，則該元素X即為所要查找的第K小的數，順序查找到第一個(gè)小于等于N-K+1的元素，則該元素X即為所要查找的第K大的數。2 計數查找算法的C語(yǔ)言實(shí)現(Count—Search)
2.1 數據結構的設計與程序
假定輸入的數組為整型數組A[1..N]，length[A]=N，數組中元素最大值為M，數組C[]記錄整數元素的大小關(guān)系。 Count-Search(int* A，int K) memest(C，0)//C[0..M]==0初始化C[] for j=1 to length[A] do C[A[j]]=C[A[j]]+1 //C[i]包含等于i的元素個(gè)數 for i=1 to M begin do C[i] = C[i]+C[i-1] //C[i]包含小于等于i的元素個(gè)數 if( C[i]>= N-K+1 ) break；//尋找到第N-K+1的元素，即為第K大的元素 end2.2 算法步驟分析
第一步：第一行的初始化操作之后，在2-3行檢查每一個(gè)輸入元素。如果一個(gè)輸入元素的值為i，即C[i]的值加1 。于是在第3行之后，C[i]中存放了等于i的元素個(gè)數（整數i=0，1，…M）。 第二步：在第4-8之后，C[i]存放了小于等于i的元素的個(gè)數。最后從數組C的首地址出發(fā)順序查找第一個(gè)使得C[i]>=N-K+1的元素，則第K大的元素即為i 。 下圖給出了Count-Search的運算過(guò)程：圖1表示初始數組A，C。圖2表示運行完程序2-3行，數組C中的元素C[i]存放的是數組A中等于i的元素個(gè)數。圖3表示運行4-8行的結果，C中元素C[i]存放的是數組A中小于等于i的元素個(gè)數。例如查找該數組第3大的數，則由于C[2]=4>=3，故元素2即為所要查找的第3大的數。 2.3 時(shí)間復雜度分析 程序2-3行時(shí)間復雜度為O(N)，第4-8行時(shí)間復雜度為O(M)，該算法的時(shí)間復雜度為T(mén)(n)= O( N+M)。如果數組A[]的最大值M與N成線(xiàn)形關(guān)系，即M=O(n)，則其時(shí)間復雜度為T(mén)(n) = O( 2N)。3 Count-Search算法與Divide-Select算法的比較
Divide-Select 的基本思想是：通過(guò)在線(xiàn)性的時(shí)間內找到一個(gè)劃分基準，使得按這個(gè)基準所劃分出的兩個(gè)子數組的長(cháng)度都至少為原數組的ξ倍（0<ξ<1是某個(gè)正常數），然后對子數組遞歸的調用Divide-Select算法，這樣就可以在線(xiàn)性的時(shí)間內完成查找任務(wù)。[6] 該算法得時(shí)間復雜度為O(6.09*N)[5]，與Count-Search算法相比較可知：Count-Search算法具有更好的時(shí)間復雜度。
4 算法測試與比較
為了證實(shí)上述結論，在A(yíng)CER TravelMate 2420 (PM730，512M內存，80G硬盤(pán))，Windows XP 平臺上編寫(xiě)了三種查找算法的子程序，進(jìn)行了相應的實(shí)驗測定，其結果如表1 所示。（實(shí)驗數據全部采用均分布的無(wú)符號整型隨機數） 表1注：以上時(shí)間單位為毫秒MS。 根據以上數據我們可以繪制出數據規模和時(shí)間的函數圖像。 觀(guān)察分析以上實(shí)驗結果，可以看出：基于快速排序的查找算法和其他算法相比較具有較差的效率；而采用了分治策略的Divide- Select查找算法的效率可以是基于快速排序的查找算法的幾十倍，其時(shí)間復雜度在圖中也反映為線(xiàn)性。而基于計數排序的查找算法（Count-Search）的時(shí)間復雜度同樣達到了線(xiàn)性，但是效率卻比Divide-Select更高，通過(guò)上述實(shí)驗可以得知：在進(jìn)行無(wú)符號整數查找時(shí)，基于計數排序的查找算法（Count-Search）在時(shí)間上是最優(yōu)的。
5 Count-Search的應用范圍
在查找無(wú)符號整數集合時(shí)，應用Count-Search算法，能夠降低查找時(shí)間復雜度。但是應用Count-Search算法時(shí)要注意：該算法只適用于整數的查找，且查找集合S的最大值M與S中元素個(gè)數N不成指數關(guān)系，即M不能遠大于N。因為當M過(guò)大時(shí)，首先內存開(kāi)銷(xiāo)就會(huì )很大，其次時(shí)間復雜度也會(huì )相應的提高。 該算法充分的運用了整數的特性，整個(gè)運算過(guò)程中無(wú)需數據的比較和交換，大大降低了算法的時(shí)間復雜度，因此該算法可以在工程統計中得到大規模運用。例如：隨著(zhù)的和應用，網(wǎng)絡(luò )中的信息量成倍的擴大，而在其中我們關(guān)注的最多的則是統計排名比較靠前的信息，如果將全部過(guò)億的統計量排序，則由于數據量過(guò)大，則會(huì )浪費大量的時(shí)間和資源。而采用Count-Search的查找算法，就可在線(xiàn)性的時(shí)間完成。6 結束語(yǔ)
本文中提出的一種基于計數排序算法的整數查找算法，該算法在運算過(guò)程中無(wú)需進(jìn)行數據的比較和交換，該算法可以應用到大規模的整數查找，算法的時(shí)間復雜度很低，而且避免的大量的數據比較和交換，同時(shí)在時(shí)間上是最優(yōu)的。 [1]崔澤鵬，李偉生. EREW PRAM模型上指數級分割待處理數據集的并行多選算法[J].北方大學(xué)學(xué)報，2003，(2)：46-49 [2]班志杰，高光來(lái). 一種Byte查找第K個(gè)元素的算法研究[J]. 內蒙古大學(xué)學(xué)報，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個(gè)元素的快速排序算法[J]. 韶關(guān)學(xué)院報，2003，(6)：32-34 [6]王曉東.《算法設計與分析》[M] .北京：清華大學(xué)出版社，2003.1：39-43【計數查找算法的研究】相關(guān)文章：
LDPC碼譯碼算法研究03-07
紅外圖像增強算法研究03-07
指紋識別算法研究03-08
FFT算法的研究與DSP實(shí)現03-07
iLBC語(yǔ)音算法的初步研究03-07
鐵路行包配裝算法研究與實(shí)現03-02
接力切換的基本算法及流程研究03-07