1.3 算法及算法分析

算法與數據結構的關系非常緊密，在算法設計時總是先要確定相應的數據結構，而在討論某一種數據結構時也必然會涉及相應的算法。下面就從算法特性、算法描述和算法分析三個方面對算法進行介紹。

1.3.1 算法特性

算法（Algorithm）是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。一個算法應該具有下列特性。

（1）有窮性：一個算法必須在有窮步之后結束，即必須在有限時間內完成。

（2）確定性：算法的每一步必須有確切的定義，無二義性，且在任何條件下算法只有唯一一條執行路徑，即對于相同的輸入只能得出相同的輸出。

（3）可行性：算法中的每一步都可以通過已經實現的基本運算的有限次執行得以實現。

（4）輸入：一個算法具有零個或多個輸入，這些輸入取自特定的數據對象集合。

（5）輸出：一個算法具有一個或多個輸出，這些輸出同輸入之間存在某種特定的關系。

算法的含義與程序十分相似，但又有區別。一個程序不一定滿足有窮性。例如，對于操作系統，只要整個系統不遭破壞，它將永遠不會停止，即使沒有作業需要處理，它仍處于動態等待中。因此，操作系統不是一個算法。另外，程序中的指令必須是機器可執行的，而算法中的指令則無此限制。算法代表了對問題的求解方法，而程序則是算法在計算機上的特定實現。一個算法若用程序設計語言來描述，就是一個程序。

算法與數據結構是相輔相成的。解決某一類特定問題的算法可以選定不同的數據結構，而且選擇恰當與否直接影響算法的效率。反之，一種數據結構的優劣由各種算法的執行效果來體現。

在算法設計時通常需要考慮以下幾個方面的要求。

（1）正確性：算法的執行結果應當滿足預先規定的功能和性能要求。正確性要求表明算法必須滿足實際需求，達到解決實際問題的目標。

（2）可讀性：一個算法應當思路清晰、層次分明、簡單明了、易讀易懂。可讀性要求表明算法主要是人與人之間交流解題思路和進行軟件設計的工具，因此可讀性必須要強。同時一個可讀性強的算法，其程序的可維護性、可擴展性都要好得多，因此，許多時候人們往往在一定程度上犧牲效率來提高可讀性。

（3）健壯性：當輸入不合法數據時，應能適當處理，不至于引起嚴重后果。健壯性要求表明算法要全面細致地考慮所有可能的邊界情況，并對這些邊界條件做出完備的處理，盡可能使算法沒有意外的情況。

（4）高效性：有效使用存儲空間和有較好的時間效率。高效性主要是指時間效率，即解決相同規模的問題時間盡可能短。

一般來說，數據結構上的基本操作主要有以下幾種。

（1）查找：尋找滿足特定條件的數據元素所在的位置。

（2）讀?。鹤x出指定位置上數據元素的內容。

（3）插入：在指定位置上添加新的數據元素。

（4）刪除：刪去指定位置上對應的數據元素。

（5）更新：修改某個數據元素的值。

1.3.2 算法描述

算法的描述方法很多，根據描述方法的不同，大致可將算法描述分為以下4種。

（1）自然語言算法描述：用人類自然語言（如中文、英文等）來描述算法，同時還可插入一些程序設計語言中的語句來描述，這種方法也稱為非形式算法描述。其優點是不需要專門學習，任何人都可以直接閱讀和理解，但直觀性很差，復雜的算法難寫難讀。

（2）框圖算法描述：這是一種圖示法，可以采用方框圖、流程圖、N-S圖等來描述算法，這種描述方法在算法研究的早期曾流行過。它的優點是直觀、易懂，但用來描述比較復雜的算法就顯得不夠方便，也不夠清晰簡潔。

（3）偽代碼算法描述：如類C語言算法描述。這種算法描述很像程序，但它不能直接在計算機上編譯、運行。這種方法很容易編寫、閱讀算法，而且格式統一，結構清晰，專業設計人員經常使用類C語言來描述算法。

（4）高級程序設計語言編寫的程序或函數：這是直接用高級語言來描述算法，它可在計算機上運行并獲得結果，使給定問題能在有限時間內被求解，通常這種算法描述也稱為程序。

【例1.5】 求兩個整數m、n(m≥n)的最大公因子，該算法的不同描述方法如下。

（1）非形式算法描述（自然語言算法描述）如下。

① [求余數]以n除m，并令r為余數(0≤r<n)；

② [判斷余數是否為零]若r=0，則結束算法，n就是最大公因子；

③ [替換并返回步驟①]若r≠0，則m ← n，n ← r，返回步驟①。

（2）算法的框圖描述如圖1.7所示。

（3）C語言函數描述如下。

int max_common_factor(int m，int n)
{
int r；
r＝m%n ；
while(r!＝0)
      { m=n；n=r；r=m%n；}
        return n ；
}

本書主要介紹算法的思路和實現過程，且盡可能地給出算法對應的C語言函數或程序（或類C語言算法描述），方便讀者閱讀或上機運行，以便更好地理解算法。

1.3.3 算法分析

所謂好的算法，除了滿足上文提到的幾個基本要求外，還必須以較少的時間與空間代價來解決相同規模的問題。因此，一個算法的優劣，可以從該算法在計算機上運行的時間和所占存儲空間來衡量和評判。算法分析就是預先分析算法在實際執行時的時空代價指標。

當一個算法被轉換成程序并在計算機上執行時，其運行所需要的時間一般取決于下列幾個因素。

（1）硬件的速度。即主機本身運行速度，主要與CPU的主頻和字長有關，也與主機系統采用的技術有關，如多機系統的運算速度一般比單機系統要快。

（2）實現算法的程序設計語言。實現算法的語言的級別越高，其執行效率相對就越低。

（3）編譯程序所生成目標代碼的質量。代碼優化較好的編譯程序所生成的程序質量較高。

（4）算法所采用的策略。采用不同設計思路與解題方法，其時空代價是不同的，一般情況下時間指標與空間指標常常是矛盾的兩個方面。

（5）問題的規模。例如，求100以內的素數與求1 000以內的素數的執行時間必然不同。

顯然，在各種因素都不能確定的情況下，很難比較算法的執行時間。也就是說，用算法的絕對執行時間來衡量算法的效率是不合適的。為此，可以將上述各種與計算機相關的軟、硬件因素都確定下來，僅對采用不同策略的算法，分析其運行代價隨問題規模大小變化的對應關系，即運行代價僅依賴于問題的規模（通常用正整數n表示），或者說它是問題規模的函數。這種函數被稱為算法的時間復雜度和空間復雜度。

1.時間復雜度

一個程序的時間復雜度（Time Complexity）是指該程序的運行時間與問題規模的對應關系。一個算法是由控制結構和原操作（所謂原操作是指從算法中選取對于所研究問題是基本運算的操作）構成的，其執行時間取決于兩者的綜合效果。為了便于比較同一問題的不同的算法，通常的做法是：從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復執行的次數為算法的時間度量。一般情況下，算法中原操作重復執行的次數是該算法所處理問題的規模n的某個函數T(n)。

【例1.6】 兩個n×n階的矩陣相乘的程序中的主要語句及其重復次數如下。

原操作語句的執行頻度

for ( i=0；i<n；i++ )
    for ( j=0；j<n；j++ )
      {  s [ i ][ j ]=0；                  n2
         for ( k=0；k<n；k++ )
            s [ i ][ j ]=s [ i ][ j ]+a [ i ][ k ] * b [ k ][ j ]；    n3
}

則該段程序的時間復雜度T(n)=cn3+n2，其中c為常量，表示算術運算時間是簡單賦值運算時間的常數倍。

許多時候，精確地計算T(n)是困難的，人們引入漸進時間復雜度在數量上估計一個算法的執行時間，也能夠達到分析算法的目的。

定義（大Ο記號）：如果存在兩個正常數c和n0，使得對所有的n（n≥n0），有：

T(n) ≤ c*f (n)

則T(n)＝Ο( f (n))。

例如，一個程序的實際執行時間為T(n)＝2.7n3+3.8n2+5.3，則T(n)＝Ο(n3)。

使用大Ο記號表示的算法的時間復雜度稱為算法的漸進時間復雜度（Asymptotic Time Complexity）。

通常用Ο(1)表示常數級時間復雜度，表明這樣的算法執行時間是恒定的，不隨問題規模的擴大而增長，顯然這是最理想的，但往往難以實現。此外，常見的漸進時間復雜度還有：

（1）O(log2n)，對數級復雜度；

（2）Ο(n)，線性復雜度；

（3）Ο(n2)和Ο(n3)，分別為平方級和立方級復雜度；

（4）Ο(2n)，指數級復雜度。

上述時間復雜度隨問題規模n的擴大其增長速度是不同的，其增長速度的快慢次序表示如下：

Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<Ο(2n)

2.空間復雜度

一個程序的空間復雜度（Space Complexity）是指程序運行從開始到結束所需的存儲量與問題規模的對應關系，記做：

S(n)=Ο(f(n))

其中n為問題的規模（或大小）。

一個上機執行的程序除了需要存儲空間來寄存本身所用指令、常數、變量和輸入數據外，還需要一些對數據進行操作的工作單元和存儲為實現計算所需信息的輔助空間。若輸入數據所占空間只取決于問題本身、和算法無關，則只需分析除輸入數據和程序之外的額外空間，否則應同時考慮輸入數據本身所需空間（和輸入數據的表示形式有關）。若額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作，輔助空間為Ο(1)。如果所占空間量依賴于特定的輸入，則除特別指明外，均按最壞情況來分析。

算法執行時間的耗費和所占存儲空間的耗費是相互矛盾的，難以兼得。即算法執行時間上的節省是以增加存儲空間為代價的，反之亦然。不過，一般而言，常常已以算法執行時間作為算法優劣的主要衡量指標。