欒磊 高捷聞

[摘 要]本文分析了查找算法在系統(tǒng)開發(fā)中的重要性，通過比較常見的靜態(tài)查找算法，得出最優(yōu)的二分法查找，是系統(tǒng)開發(fā)過程中查找算法的首選。

[關(guān)鍵詞]算法 順序查找二分法查找 分塊查找

一、系統(tǒng)算法概述

算法是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量。

一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征： 1.有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束； 2.確切性：算法的每一步驟必須有確切的定義； 3.輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對象的初始情況； 4.輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果;5.可行性：算法原則上能夠精確地運(yùn)行，有限次運(yùn)算后即可完成。

由此可以看出，一個(gè)算法的好壞對于系統(tǒng)能否成功有著決定性的作用。對于任何一個(gè)系統(tǒng)設(shè)計(jì)人員來說，系統(tǒng)算法的設(shè)計(jì)都是考慮問題的重中之重。因此算法的優(yōu)良直接影響著系統(tǒng)的使用價(jià)值。

二、算法復(fù)雜性分析

算法的復(fù)雜性是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上面，所需的資源越多，我們就說該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。計(jì)算機(jī)的資源，最重要的是時(shí)間和空間（即存儲(chǔ)器）資源。因而，算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。

不言而喻，對于任意給定的問題，設(shè)計(jì)出復(fù)雜性盡可能地的算法是我們在設(shè)計(jì)算法是追求的一個(gè)重要目標(biāo)；另一方面，當(dāng)給定的問題已有多種算法時(shí)，選擇其中復(fù)雜性最低者，是我們在選用算法適應(yīng)遵循的一個(gè)重要準(zhǔn)則。因此，算法的復(fù)雜性分析對算法的設(shè)計(jì)或選用有著重要的指導(dǎo)意義和實(shí)用價(jià)值。

三、查找算法概述

查找是確定數(shù)據(jù)元素集合中是否存在數(shù)據(jù)元素等于特定元素或者是否存在元素滿足某種給定特征的過程。要進(jìn)行查找，必須知道待查找對象的特征，也就是要知道待查找數(shù)據(jù)元素的關(guān)鍵字。一般地，衡量查找算法效率的標(biāo)準(zhǔn)是平均查找長度ASL，也就是為確定某一結(jié)點(diǎn)在數(shù)據(jù)集合中的位置，給定值與集合中的結(jié)點(diǎn)關(guān)鍵字所需進(jìn)行的比較次數(shù)。對于具有n個(gè)數(shù)據(jù)元素的集合，查找某元素成功的平均查找長度為：ASL=其中n是查找表中結(jié)點(diǎn)的個(gè)數(shù)；Ci為查找第i個(gè)元素的概率=1。在分析查找算法的復(fù)雜性時(shí)，若未特別說明，認(rèn)為每個(gè)結(jié)點(diǎn)具有相同的查找概率，即p1=p2..=pn=1/n。查找算法在各類程序中應(yīng)用非常廣泛。查找算法主要有兩大類：一類是基于靜態(tài)查找表上的操作，另一類是基于動(dòng)態(tài)查找表上的操作。本系統(tǒng)主要是基于靜態(tài)查找表上的操作，其主要使用的查找算法有：順序查找、二分法查找與分塊查找。

1.順序查找。順序查找是一種最簡單的查找方法。它的基本思想是：從表的一端開始，順序進(jìn)行查找，直到找到的結(jié)點(diǎn)關(guān)鍵字與給定的Key相等為止，若查找結(jié)束后，仍未找到關(guān)鍵字等于Key的結(jié)點(diǎn)，則查找失敗。順序查找算法的缺點(diǎn)是查找時(shí)間長。其查找成功時(shí)的平均查找長度為：

在查找失敗時(shí)，算法的平均查找長度為：

2.二分法查找。二分法查找又稱為折半查找，采用二分法查找可以大大提高查找效率，它要求線性表的結(jié)點(diǎn)按其關(guān)鍵字從小到大（或從大到?。┌葱蚺帕胁⒉捎庙樞虼鎯?chǔ)結(jié)構(gòu)。二分法查找的基本過程是：設(shè)L[low..high]是當(dāng)前的查找區(qū)間，首先讓待查找的數(shù)據(jù)元素同線性表中間結(jié)點(diǎn)mid=[(low+high)/2]的關(guān)鍵字相比較，若比較相等，則查找成功并結(jié)束二分查找；若待查找的數(shù)據(jù)元素比中間結(jié)點(diǎn)的關(guān)鍵字要小，則在線性表的前半部分L[low...mid-1]進(jìn)行二分查找；反之，則在線性表的后半部分[mid+1...high]進(jìn)行二分查找，直到找到滿足條件的結(jié)點(diǎn)或者確定表中沒有這樣的結(jié)點(diǎn)為止。

二分查找每經(jīng)過一次比較就將查找范圍縮小一半，因此比較次數(shù)是log2n這個(gè)量級(jí)的。不妨設(shè)n=2k-1(2的K次方)，容易看出，線性表至多被平分k次即可完成查找。也即，在最壞的情況下，查找算法k=log2（n+1）次即可結(jié)束。二分查找的平均查找次數(shù)為：

用數(shù)學(xué)歸納法容易證明：

所以

不論查找成功或失敗，二分查找比順序查找要快的多。

3.分塊查找。分塊查找又稱為索引順序查找，他是順序查找算法與二分查找算法的一種結(jié)合，其基本思想是：首先把線性表分成若干塊，在每塊中，結(jié)點(diǎn)的存放不一定有序，但塊與塊之間必須是分塊有序的。分塊查找方法通過將查找縮小在某個(gè)塊中從而提高了查找的效率，其查找的效率由兩部分組成，一是為確定待查找元素所在塊而對索引表查找的平均查找長度E1，二是塊內(nèi)查找所需的平均查找長度Eb。

若以順序查找來確定分塊，則分塊查找成功時(shí)的平均查找長度為：

ASLids=E1+Eb= =（（n/s）+s）/2 +1

n：總元素個(gè)數(shù) ，b：n個(gè)元素被分成的塊數(shù)，則每塊中的元素個(gè)數(shù)就是s=n/b。

若以二分查找來確定分塊，則分塊查找成功時(shí)的平均查找長度為：

ASLids= E1+Eb≈log2(n/s +1)+s/2

由此可見，分塊查找比順序查找要快，但比二分查找要慢。

在最壞的情況下，順序查找算法和二分查找算法在解決同一個(gè)問題時(shí)，兩個(gè)算法所需要檢測的分量個(gè)數(shù)卻大不相同，前者要m=2 k個(gè)，后者只要k+1個(gè)?？梢娝惴ǘ植檎宜惴ū人惴樞虿檎宜惴ǜ咝У枚?。

解同一個(gè)問題，算法不同，則計(jì)算的工作量也不同，所需的計(jì)算時(shí)間隨之不同，即復(fù)雜性不同。上圖是運(yùn)行這兩種算法的時(shí)間曲線。該圖表明，當(dāng)m適當(dāng)大（m>m0）時(shí)，二分查找算法（B_Search）比順序查找算法（Search）省時(shí)，而且當(dāng)m更大時(shí)，節(jié)省的時(shí)間急劇增加。

四、結(jié)論

我們引入算法復(fù)雜性的概念是為了比較解決同一個(gè)問題的不同算法的效率，而不想去比較運(yùn)行該算法的計(jì)算機(jī)的性能。因而，不應(yīng)該取算法運(yùn)行的實(shí)例時(shí)間作為算法復(fù)雜性的尺度。我們希望，盡量單純地反映作為算法精髓的計(jì)算方法本身的效率，而且在不實(shí)際運(yùn)行該算法的情況下就能分析出它所需要的時(shí)間和空間。

參考文獻(xiàn)：

[1]郭紹忠.基于GPU的單源最短路徑算法的設(shè)計(jì)與實(shí)現(xiàn).商場現(xiàn)代化，2011,9

[2]李云清.數(shù)據(jù)結(jié)構(gòu)（C語言版）.人民郵電出版社，2006,8