計(jì)數(shù)查找算法的研究

《計(jì)數(shù)查找算法的研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、計(jì)數(shù)查找算法的研究摘要查找第K大的元素的問題在計(jì)算機(jī)查找計(jì)數(shù)中占有很重要的地位。若直接進(jìn)行排序，則算法平均時(shí)間復(fù)雜度為O(N*Lg(N))。但是比較好的策略有求第K大的元素的經(jīng)典算法——基于分治思想的Divide-Select[1][6]，算法的時(shí)間復(fù)雜度為O(6.09*N)[5]。由于基于比較的排序算法在最壞的情況之下，都需要進(jìn)行N*Lg(N)次比較[3]，故本文提出了一種基于非比較算法的無符號整數(shù)查找算法——Count-Search（計(jì)數(shù)查找算法）。該算法應(yīng)用于無符號整數(shù)的查找，算法的平均時(shí)間復(fù)雜度為O(2*N)。關(guān)鍵字非比

2、較；查找；排序；時(shí)間復(fù)雜度；計(jì)數(shù)；整數(shù)1算法的基本思想通常的排序算法在空間和時(shí)間復(fù)雜度一定的情況下的時(shí)間開銷主要是關(guān)鍵字之間的比較和記錄的移動?；谟?jì)數(shù)排序的查找算法（Count-Search）的實(shí)現(xiàn)在整個(gè)過程無需進(jìn)行數(shù)據(jù)的比較，算法的時(shí)間復(fù)雜度為O(2*N)。該算法的基本原理是：根據(jù)無符號整數(shù)的大小可以和數(shù)組元素的下標(biāo)對應(yīng)的原則，在程序中可以用整數(shù)數(shù)組來儲存元素的大小關(guān)系。對于一個(gè)大小為N的整型數(shù)組a[]，對于每一個(gè)元素x，用數(shù)組中的元素a[x]記錄下小于等于它的元素個(gè)數(shù)，當(dāng)要找的是集合中第K個(gè)大的元素時(shí)，則只需找到該數(shù)組中第

3、N-K+1小的元素。即只需要找到該數(shù)組中第一個(gè)大于或等于N-K+1的元素，該元素的下標(biāo)即為第K大的數(shù)。該算法具體可以描述為：假設(shè)n個(gè)輸入元素的每一個(gè)都是介于0到M之間的整數(shù)，此處M為某個(gè)無符號整數(shù)。(1)對于每一個(gè)輸入的元素X，首先確定出等于X的元素個(gè)數(shù)。(2)對于每一個(gè)元素X，確定小于等于X的元素個(gè)數(shù)。(3)從數(shù)組首地址出發(fā)順序查找到第一個(gè)小于等于K的元素，則該元素X即為所要查找的第K小的數(shù)，順序查找到第一個(gè)小于等于N-K+1的元素，則該元素X即為所要查找的第K大的數(shù)。2計(jì)數(shù)查找算法的C語言實(shí)現(xiàn)(Count—Search)2.

4、1數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與程序假定輸入的數(shù)組為整型數(shù)組A[1..N]，length[A]=N，數(shù)組中元素最大值為M，數(shù)組C[]記錄整數(shù)元素的大小關(guān)系。Count-Search(int*A，intK)memest(C，0)//C[0..M]==0初始化C[]forj=1tolength[A]doC[A[j]]=C[A[j]]+1//C[i]包含等于i的元素個(gè)數(shù)fori=1toMbegindoC[i]=C[i]+C[i-1]//C[i]包含小于等于i的元素個(gè)數(shù)if(C[i]>=N-K+1)break；//尋找到第N-K+1的元素，即為

5、第K大的元素end2.2算法步驟分析第一步：第一行的初始化操作之后，在2-3行檢查每一個(gè)輸入元素。如果一個(gè)輸入元素的值為i，即C[i]的值加1。于是在第3行之后，C[i]中存放了等于i的元素個(gè)數(shù)（整數(shù)i=0，1，…M）。第二步：在第4-8之后，C[i]存放了小于等于i的元素的個(gè)數(shù)。最后從數(shù)組C的首地址出發(fā)順序查找第一個(gè)使得C[i]>=N-K+1的元素，則第K大的元素即為i。下圖給出了Count-Search的運(yùn)算過程：圖1表示初始數(shù)組A，C。圖2表示運(yùn)行完程序2-3行，數(shù)組C中的元素C[i]存放的是數(shù)組A中等于i的元素個(gè)數(shù)

6、。圖3表示運(yùn)行4-8行的結(jié)果，C中元素C[i]存放的是數(shù)組A中小于等于i的元素個(gè)數(shù)。例如查找該數(shù)組第3大的數(shù)，則由于C[2]=4>=3，故元素2即為所要查找的第3大的數(shù)。2.3時(shí)間復(fù)雜度分析程序2-3行時(shí)間復(fù)雜度為O(N)，第4-8行時(shí)間復(fù)雜度為O(M)，該算法的時(shí)間復(fù)雜度為T(n)=O(N+M)。如果數(shù)組A[]的最大值M與N成線形關(guān)系，即M=O(n)，則其時(shí)間復(fù)雜度為T(n)=O(2N)。3Count-Search算法與Divide-Select算法的比較Divide-Select的基本思想是：通過在線性的時(shí)間內(nèi)找到一個(gè)

7、劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的兩個(gè)子數(shù)組的長度都至少為原數(shù)組的ξ倍（0<ξ<1是某個(gè)正常數(shù)），然后對子數(shù)組遞歸的調(diào)用Divide-Select算法，這樣就可以在線性的時(shí)間內(nèi)完成查找任務(wù)。[6]該算法得時(shí)間復(fù)雜度為O(6.09*N)[5]，與Count-Search算法相比較可知：Count-Search算法具有更好的時(shí)間復(fù)雜度。4算法測試與比較為了證實(shí)上述結(jié)論，在ACERTravelMate2420(PM730，512M內(nèi)存，80G硬盤)，].北京：機(jī)械工業(yè)出版社。2006.9：98-99[4]MuhammadH

8、.Alsualparallelalgorithmforthemultiselectionproblem[J].Parallelputing，2001，(27)：861—865[5]江華.求第K個(gè)元素的快速排序算法[J].韶關(guān)學(xué)院報(bào)，2003，(6)：32-34[