<menuitem id="r3jhr"></menuitem><noscript id="r3jhr"><progress id="r3jhr"><code id="r3jhr"></code></progress></noscript>

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

      時(shí)間:2021-06-10 14:19:11 論文 我要投稿

      計(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)。

      計(jì)數(shù)查找算法研究精選論文

        關(guān)鍵字:非比較;查找;排序;時(shí)間復(fù)雜度;計(jì)數(shù);整數(shù)

        1算法的基本思想

        通常的排序算法在空間和時(shí)間復(fù)雜度一定的情況下的時(shí)間開銷主要是關(guān)鍵字之間的比較和記錄的移動(dòng)。基于計(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ù)組中第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.1數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與程序

        2.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ù)。圖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è)劃分基準(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硬盤),WindowsXP平臺上編寫了三種查找算法的子程序,進(jìn)行了相應(yīng)的實(shí)驗(yàn)測定,其結(jié)果如表1所示。(實(shí)驗(yàn)數(shù)據(jù)全部采用均分布的無符號整型隨機(jī)數(shù))

        注:以上時(shí)間單位為毫秒MS。

        根據(jù)以上數(shù)據(jù)我們可以繪制出數(shù)據(jù)規(guī)模和時(shí)間的函數(shù)圖像。

        觀察分析以上實(shí)驗(yàn)結(jié)果,可以看出:基于快速排序的查找算法和其他算法相比較具有較差的效率;而采用了分治策略的Divide-Select查找算法的效率可以是基于快速排序的查找算法的幾十倍,其時(shí)間復(fù)雜度在圖中也反映為線性。而基于計(jì)數(shù)排序的查找算法(Count-Search)的時(shí)間復(fù)雜度同樣達(dá)到了線性,但是效率卻比Divide-Select更高,通過上述實(shí)驗(yàn)可以得知:在進(jìn)行無符號整數(shù)查找時(shí),基于計(jì)數(shù)排序的查找算法(Count-Search)在時(shí)間上是最優(yōu)的。

        5Count-Search的應(yīng)用范圍

        在查找無符號整數(shù)集合時(shí),應(yīng)用Count-Search算法,能夠降低查找時(shí)間復(fù)雜度。但是應(yīng)用Count-Search算法時(shí)要注意:該算法只適用于整數(shù)的查找,且查找集合S的最大值M與S中元素個(gè)數(shù)N不成指數(shù)關(guān)系,即M不能遠(yuǎn)大于N。因?yàn)楫?dāng)M過大時(shí),首先內(nèi)存開銷就會很大,其次時(shí)間復(fù)雜度也會相應(yīng)的提高。

        該算法充分的運(yùn)用了整數(shù)的特性,整個(gè)運(yùn)算過程中無需數(shù)據(jù)的比較和交換,大大降低了算法的時(shí)間復(fù)雜度,因此該算法可以在工程統(tǒng)計(jì)中得到大規(guī)模運(yùn)用。例如:隨著網(wǎng)絡(luò)的發(fā)展和應(yīng)用,網(wǎng)絡(luò)中的信息量成倍的擴(kuò)大,而在其中我們關(guān)注的最多的則是統(tǒng)計(jì)排名比較靠前的信息,如果將全部過億的統(tǒng)計(jì)量排序,則由于數(shù)據(jù)量過大,則會浪費(fèi)大量的時(shí)間和資源。而采用Count-Search的查找算法,就可在線性的時(shí)間完成。

        6結(jié)束語

        本文中提出的一種基于計(jì)數(shù)排序算法的整數(shù)查找算法,該算法在運(yùn)算過程中無需進(jìn)行數(shù)據(jù)的比較和交換,該算法可以應(yīng)用到大規(guī)模的整數(shù)查找,算法的時(shí)間復(fù)雜度很低,而且避免的大量的數(shù)據(jù)比較和交換,同時(shí)在時(shí)間上是最優(yōu)的。

        參考文獻(xiàn)

        [1]崔澤鵬,李偉生.EREWPRAM模型上指數(shù)級分割待處理數(shù)據(jù)集的并行多選算法[J].北方交通大學(xué)學(xué)報(bào),2003,(2):46-49

        [2]班志杰,高光來.一種Byte查找第K個(gè)元素的算法研究[J].內(nèi)蒙古大學(xué)學(xué)報(bào),2004,(3):322-324

        [3]ThomasH.CormenCharlesE.Leiserson.《算法導(dǎo)論》[M].北京:機(jī)械工業(yè)出版社。2006.9:98-99

        [4]MuhammadH.Alsuwaiyel.Anoptimalparallelalgorithmforthemultiselectionproblem[J].ParallelComputing,2001,(27):861—865

        [5]江華.求第K個(gè)元素的快速排序算法[J].韶關(guān)學(xué)院報(bào),2003,(6):32-34

        [6]王曉東.《算法設(shè)計(jì)與分析》[M].北京:清華大學(xué)出版社,2003.1:39-43

      【計(jì)數(shù)查找算法研究論文】相關(guān)文章:

      近場聲源定位算法研究論文06-13

      三對角系統(tǒng)算法研究的論文04-14

      關(guān)于運(yùn)動(dòng)估計(jì)快速搜索算法的研究的論文02-27

      論文:基于粒子群算法的雙子支持向量機(jī)研究06-13

      基于大氣散射理論的視頻去霧算法的研究論文06-13

      基于遺傳算法的車牌定位技術(shù)研究論文04-16

      智能計(jì)算的經(jīng)典算法解析論文06-13

      作業(yè)成本的計(jì)算法論文06-13

      算法設(shè)計(jì)與分析課程論文04-22

      久久亚洲中文字幕精品一区四_久久亚洲精品无码av大香_天天爽夜夜爽性能视频_国产精品福利自产拍在线观看
      <menuitem id="r3jhr"></menuitem><noscript id="r3jhr"><progress id="r3jhr"><code id="r3jhr"></code></progress></noscript>
        无遮挡很黄很爽免费国产 | 精品一区二区三区亚洲欧洲 | 中文字幕在线乱码页 | 中文字字幕在线无线码 | 亚洲国产精品人久久 | 欧美成a高清在线观看 |