計數查詢演算法研究精選論文
摘要：查詢第K大的元素的問題在計算機查詢計數中佔有很重要的地位。若直接進行排序，則演算法平均時間複雜度為O(N*Lg(N))。但是比較好的策略有求第K大的元素的經典演算法——基於分治思想的Divide-Select[1][6]，演算法的時間複雜度為O(6.09*N)[5]。由於基於比較的排序演算法在最壞的情況之下，都需要進行N*Lg(N)次比較[3]，故本文提出了一種基於非比較演算法的無符號整數查詢演算法——Count-Search（計數查詢演算法）。該演算法應用於無符號整數的查詢，演算法的平均時間複雜度為O(2*N)。
關鍵字：非比較；查詢；排序；時間複雜度；計數；整數
1演算法的基本思想
通常的排序演算法在空間和時間複雜度一定的情況下的時間開銷主要是關鍵字之間的比較和記錄的移動。基於計數排序的查詢演算法（Count-Search）的實現在整個過程無需進行資料的比較，演算法的時間複雜度為O(2*N)。該演算法的基本原理是：
根據無符號整數的大小可以和陣列元素的下標對應的原則，在程式中可以用整數陣列來儲存元素的大小關係。對於一個大小為N的整型陣列a[]，對於每一個元素x，用陣列中的元素a[x]記錄下小於等於它的元素個數，當要找的是集合中第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語言實現(Count—Search)
2.1資料結構的設計與程式
2.2演算法步驟分析
第一步：第一行的初始化操作之後，在2-3行檢查每一個輸入元素。如果一個輸入元素的值為i，即C[i]的值加1。於是在第3行之後，C[i]中存放了等於i的元素個數（整數i=0，1，…M）。
第二步：在第4-8之後，C[i]存放了小於等於i的元素的個數。最後從陣列C的首地址出發順序查詢第一個使得C[i]>=N-K+1的元素，則第K大的元素即為i。
下圖給出了Count-Search的運算過程：圖1表示初始陣列A，C。圖2表示執行完程式2-3行，陣列C中的元素C[i]存放的是陣列A中等於i的元素個數。圖3表示執行4-8行的結果，C中元素C[i]存放的是陣列A中小於等於i的元素個數。例如查詢該陣列第3大的數，則由於C[2]=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)。
3Count-Search演算法與Divide-Select演算法的比較
Divide-Select的基本思想是：透過線上性的時間內找到一個劃分基準，使得按這個基準所劃分出的兩個子陣列的長度都至少為原陣列的ξ倍（0<ξ<1是某個正常數），然後對子陣列遞迴的呼叫Divide-Select演算法，這樣就可以線上性的時間內完成查詢任務。[6]
該演算法得時間複雜度為O(6.09*N)[5]，與Count-Search演算法相比較可知：Count-Search演算法具有更好的時間複雜度。
4演算法測試與比較
為了證實上述結論，在ACERTravelMate2420(PM730，512M記憶體，80G硬碟)，WindowsXP平臺上編寫了三種查詢演算法的子程式，進行了相應的實驗測定，其結果如表1所示。（實驗資料全部採用均分佈的無符號整型隨機數）
注：以上時間單位為毫秒MS。
根據以上資料我們可以繪製出資料規模和時間的函式影象。
觀察分析以上實驗結果，可以看出：基於快速排序的查詢演算法和其他演算法相比較具有較差的效率；而採用了分治策略的Divide-Select查詢演算法的效率可以是基於快速排序的查詢演算法的幾十倍，其時間複雜度在圖中也反映為線性。而基於計數排序的查詢演算法（Count-Search）的時間複雜度同樣達到了線性，但是效率卻比Divide-Select更高，透過上述實驗可以得知：在進行無符號整數查詢時，基於計數排序的查詢演算法（Count-Search）在時間上是最優的。
5Count-Search的應用範圍
在查詢無符號整數集合時，應用Count-Search演算法，能夠降低查詢時間複雜度。但是應用Count-Search演算法時要注意：該演算法只適用於整數的查詢，且查詢集合S的最大值M與S中元素個數N不成指數關係，即M不能遠大於N。因為當M過大時，首先記憶體開銷就會很大，其次時間複雜度也會相應的提高。
該演算法充分的運用了整數的特性，整個運算過程中無需資料的比較和交換，大大降低了演算法的時間複雜度，因此該演算法可以在工程統計中得到大規模運用。例如：隨著網路的發展和應用，網路中的資訊量成倍的擴大，而在其中我們關注的最多的則是統計排名比較靠前的資訊，如果將全部過億的統計量排序，則由於資料量過大，則會浪費大量的時間和資源。而採用Count-Search的查詢演算法，就可線上性的時間完成。
6結束語
本文中提出的一種基於計數排序演算法的整數查詢演算法，該演算法在運算過程中無需進行資料的比較和交換，該演算法可以應用到大規模的整數查詢，演算法的時間複雜度很低，而且避免的大量的資料比較和交換，同時在時間上是最優的。
參考文獻
[1]崔澤鵬，李偉生.EREWPRAM模型上指數級分割待處理資料集的並行多選演算法[J].北方交通大學學報，2003，(2)：46-49
[2]班志傑，高光來.一種Byte查詢第K個元素的演算法研究[J].內蒙古大學學報，2004，(3)：322-324
[3]ThomasH.CormenCharlesE.Leiserson.《演算法導論》[M].北京：機械工業出版社。2006.9：98-99
[4]MuhammadH.Alsuwaiyel.Anoptimalparallelalgorithmforthemultiselectionproblem[J].ParallelComputing，2001，(27)：861—865
[5]江華.求第K個元素的快速排序演算法[J].韶關學院報，2003，(6)：32-34
[6]王曉東.《演算法設計與分析》[M].北京：清華大學出版社，2003.1：39-43