基于系統的查找算法研究

[摘 要]本文分析了查找算法在系統開發中的重要性，通過比較常見的靜態查找算法，得出最優的二分法查找，是系統開發過程中查找算法的首選。

[關鍵詞]算法 順序查找 二分法查找 分塊查找

一、系統算法概述

算法是一系列解決問題的清晰指令，也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。不同的算法可能用不同的時間、空間或效率來完成同樣的任務。一個算法的優劣可以用空間復雜度與時間復雜度來衡量。

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

由此可以看出，一個算法的好壞對于系統能否成功有著決定性的作用。對于任何一個系統設計人員來說，系統算法的設計都是考慮問題的重中之重。因此算法的優良直接影響著系統的使用價值。

二、算法復雜性分析

算法的復雜性是算法效率的度量，是評價算法優劣的重要依據。一個算法的復雜性的高低體現在運行該算法所需要的計算機資源的多少上面，所需的資源越多，我們就說該算法的復雜性越高；反之，所需的資源越低，則該算法的復雜性越低。計算機的資源，最重要的是時間和空間（即存儲器）資源。因而，算法的復雜性有時間復雜性和空間復雜性之分。

不言而喻，對于任意給定的問題，設計出復雜性盡可能地的算法是我們在設計算法是追求的一個重要目標；另一方面，當給定的問題已有多種算法時，選擇其中復雜性最低者，是我們在選用算法適應遵循的一個重要準則。因此，算法的復雜性分析對算法的設計或選用有著重要的指導意義和實用價值。

三、查找算法概述

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

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

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

2.二分法查找。二分法查找又稱為折半查找，采用二分法查找可以大大提高查找效率，它要求線性表的結點按其關鍵字從小到大（或從大到小）按序排列并采用順序存儲結構。二分法查找的基本過程是：設L[low..high]是當前的查找區間，首先讓待查找的數據元素同線性表中間結點mid=[(low+high)/2]的關鍵字相比較，若比較相等，則查找成功并結束二分查找；若待查找的數據元素比中間結點的關鍵字要小，則在線性表的前半部分L[low...mid-1]進行二分查找；反之，則在線性表的后半部分[mid+1...high]進行二分查找，直到找到滿足條件的結點或者確定表中沒有這樣的結點為止。

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

用數學歸納法容易證明：

所以

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

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

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

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

n：總元素個數 ，b：n個元素被分成的塊數，則每塊中的元素個數就是s=n/b。

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

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

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

在最壞的情況下，順序查找算法和二分查找算法在解決同一個問題時，兩個算法所需要檢測的分量個數卻大不相同，前者要m=2 k個，后者只要k+1個。可見算法二分查找算法比算法順序查找算法高效得多。

解同一個問題，算法不同，則計算的工作量也不同，所需的計算時間隨之不同，即復雜性不同。上圖是運行這兩種算法的時間曲線。該圖表明，當m適當大（m>m0）時，二分查找算法（B_Search）比順序查找算法（Search）省時，而且當m更大時，節省的時間急劇增加。

四、結 論

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

參考文獻：

[1]郭紹忠.基于GPU的單源最短路徑算法的設計與實現.商場現代化，2011，9

[2]李云清.數據結構（C語言版）.人民郵電出版社，2006，8