1.2 算法和算法分析

1.2.1 算法的描述

算法（algorithm）定義：為了解決某一類問題而設計的一個有限長的操作序列。一個算法必須滿足以下5個重要特性。

① 有窮性。算法對于任意合法的輸入值，在執行有限步之后一定能結束。

② 確定性。算法中的每一個操作必須有確切的含義，無二義性，并在任何條件下，算法都只有一條執行路徑。

③ 可行性。算法中的所有操作都可通過已經實現的基本運算有限次地實現。

④ 輸入。算法具有零個或多個輸入，這些輸入為一組特定的數據對象集合。

⑤ 輸出。算法具有一個或多個輸出，它是一組與“輸入”有確定關系的量值。

1.2.2 算法設計的要求

（1）正確性（correctness）

算法的執行結果應當滿足預先規定的4個要求：①程序不含語法錯誤；② 程序對于幾組輸入數據能夠得出滿足規格說明要求的結果；③程序對于精心選擇的典型、苛刻且帶有刁難性的幾組輸入數據能夠得出滿足規格說明要求的結果；④程序對于一切合法的輸入數據都能產生滿足規格說明要求的結果。

（2）可讀性（readability）

算法應有助于人們閱讀、理解和調試，晦澀難懂的算法易于隱藏較多錯誤，難以調試和修改。

（3）健壯性（robustness）

當輸入不合法的數據時，算法能夠做出適當的反應或處理，不至于產生莫名其妙的結果。同時，處理出錯的方法應該是返回一個表示錯誤或錯誤性質的值，并終止程序的執行，以便在更高的抽象層次上進行處理。

（4）時空效率（efficiency）

要求算法執行的時間應該盡可能短、算法執行過程中占用的存儲空間應該盡可能少。時空要求與求解問題的規模有關，兩者通常相互矛盾，因此，應在它們之間有所平衡。

1.2.3 算法分析

算法分析的兩個主要方面是分析算法的時間復雜度和空間復雜度，主要考察算法的時間效率和空間效率，以便比較和改進算法。通常，在算法的運算空間較為充裕的情況下，更多地關注算法的時間復雜度。

1.時間復雜度

算法執行的時間可通過依據該算法編制的程序在計算機上從開始運行到結束運行所消耗的時間來度量，也就是算法中每條語句的執行時間之和。由于每條語句的執行時間是該語句重復執行的次數或頻度（frequency count）與該語句執行時間的乘積，而語句的執行時間又與機器性能、編譯程序等諸多因素有關，難以統一和確定。因此，假設每條語句的執行時間為一個單位時間，則算法的執行時間為算法中所有語句的頻度之和。

一般而言，算法中基本操作的頻度是問題規模 n（如算法所處理的矩陣的階數，線性表的長度）的某個函數 f(n)，算法的時間量度記作 T(n)=O(f(n))，它表示隨問題規模 n 的增大，算法的執行時間增長率與 f(n)的增長率相同，稱為算法的漸進時間復雜度（asymptotic time complexity），簡稱時間復雜度。同時，要全面地分析算法，需要分別考慮算法在最壞情況、最好情況以及平均情況下的時間代價。對于最壞情況下的時間復雜度，主要采用大寫數學符號O表示法來描述。一般定義為：當且僅當存在正整數c和n0，使得T(n)≤c f(n)對所有的n≥n0成立，則稱該算法的漸進時間復雜度為T(n)=O(f(n))。

在一般情況下，對于一個問題（算法）只需選擇一種基本操作來討論算法的時間復雜度即可，有時也需要同時考慮幾種基本操作，甚至可對不同的操作賦以不同權值，以反映執行不同操作所需的相對時間，這種做法便于綜合比較解決同一問題的兩種完全不同的算法。由于算法的時間復雜度考慮的只是對于問題規模n的增長率，因此在難以精確計算基本操作執行次數（或語句頻度）的情況下，只需求出它關于n的增長率或階即可。

【例1-3】 如何進行算法的時間復雜度分析。

首先介紹計算增長率的加法規則和乘法規則。設 T1(n)和 T2(n)分別是程序段P1和P2的運行時間，且 T1(n)=O(f(n))，T2(n)=O(g(n))，即 T1(n)是 f(n)的函數，T2(n)是 g(n)的函數（O函數定義見后），則執行P1 之后緊接著執行P2 的運行時間為：T1(n)+T2(n)=O(max{f(n)，g(n)})，稱為加法規則；T1(n)×T2(n)=O[f(n)×g(n)]，稱為乘積規則。一般來說，分析程序的時間復雜度是，先求出各模塊（各語句）的運行時間，再求整個程序的運行時間，它可表示成唯一參數——輸入數據的規模n的函數。具體可遵循以下規則。

① 每個賦值或讀/寫語句的運行時間通常是O(1)。如果賦值語句的右部為函數調用，則要考慮計算函數值所消耗的時間。

② 序列語句的運行時間由加法規則確定。

③ 語句if B then S1 else S2的運行時間為條件B的測試時間（通常取O(1)）加上兩個分支語句S1、S2運行時間的較大者。若無else S2，則只需加上S1的運行時間。

④ 循環語句的運行時間是循環體本身的運行時間和計算循環參數、測試循環終止條件及跳回循環開頭所花的時間，后一部分通常取 O(1)。遇到多層循環時，要由內層向外層逐層分析。在分析外層循環時間時，內層循環的運行時間應該是已知的，可把內循環看成是外循環體的一部分。

⑤ 若程序中只包含非遞歸過程，則從沒有調用語句（對函數也認為是調用）的過程開始，計算所有這種過程的運行時間。然后考慮有調用語句的任一過程P，在P調用的全部過程的運行時間都算完之后，即可開始計算P的運行時間。若在程序中有遞歸過程，則可令每個遞歸過程對應于一個未知的時間開銷函數T(n)，其中n是過程參數的長度。之后，列出一個關于T的遞歸方程并求解之。

【例1-4】 下面是一個n×n階矩陣A自乘得到B=A×A的算法，分析其時間復雜度。

            int  A[n][n]；                                                        //全局數組
            void  mtxmlt（）
            {        int B[n][n]；                                                //語句頻度
                    for（int i=0；i<n；i++）                                     //n+1
                            for（int j=0；j<n；j++）                              //n×（n+1）
                            {   B[i][j]=0；                                       //n×n
                                for（int k=0；k<n；k++）                          //n2×（n+1）
                                    B[i][j]=B[i][j]+A[i][k]*A[k][j]；             //n×n×n
                            }
            }

時間復雜度 T(n)=n+1+n(n+1)+n×n+n2(n+1)+n×n×n=2n3+3n2+2n+1。當 n→∞時，T(n)∝n3，故算法時間復雜度的數量級為O(n3)。

【例1-5】 已知算法如下，求帶下劃線語句的頻度。

            int i=0；
                while（（i<n）&&（x!=A[i]））i++；
                  if（A[i]==x） return i；

在此程序段中，語句的頻度不僅是 n 的函數，而且與 x 及數組A中各分量的值有關。在這種情況下，通?？紤]最壞的情況。由于while循環執行的最大數為n-1，因此下劃線語句頻度為n-1。

【例1-6】 分析計算n！的遞歸函數fact(n)的時間復雜度。

            long  fact（int n）
            {    if（n==1） return 1；
                return  fact（n-1）*n；
            }

遞歸函數fact(n)的輸入規模是 n，設 T(n)是fact(n)的時間開銷函數。在上述算法中，if語句條件測試及語句return的運行時間是O(1)，遞歸調用fact(n-1)的運行時間是T(n-1)。假設兩個整數相乘和賦值操作的運算時間是 O(1)，故return fact(n-1)*n 的運行時間是O(1)+T(n-1)。因此，對于常數 C 和 D 有 T(n)=D，n≤1；T(n)=C+T(n-1)，n＞1?，F在來解這個遞歸方程。設 n＞2，對上式中 T(n-1)進行展開有 T(n-1)=C+T(n-2)，代入 T(n)中，有T(n)=2C+T(n-2)，再展開 T(n-2)得 T(n)=3C+T(n-3)。一般有 T(n)=iC+T(n-i)，n＞i。最后，當i=n-1時，得T(n)=C(n-1)+T(1)=C(n-1)+D。當n→∞時，T(n)∝n。

2.空間復雜度

算法在執行時需要占用一定的存儲空間，這些空間除了包括程序、輸入數據、常數、變量所占的空間外，還包括算法對輸入數據進行運算以及為實現運算所需信息的額外空間。額外空間與算法的質量密切相關，好的算法既節省時間又節省額外空間。如果算法的輸入數據所占用的空間只取決于問題本身，與算法無關，則算法的存儲空間只需要分析除輸入數據和程序之外的額外空間；否則，應同時考慮輸入數據本身所需空間（與輸入數據的表示形式有關）。通常，只有完成同一功能的幾個算法之間才具有可比性，因此這些輸入數據所占用的空間不用進行比較，只需比較那些輔助的或附加的存儲空間即可。

類似于算法的時間復雜度，一般以空間復雜度（space complexity）作為算法所需存儲空間的量度，記作S(n)=O(f(n))，其中n為問題的規模（或大小）。在大多數的算法設計中，時間效率和空間效率兩者很難兼得，設計者往往需要根據具體的問題進行權衡，有時會用更多的存儲空間來換取時間，有的時候又會用增加算法執行時間來減少所需的存儲空間。

【例1-7】 如何進行算法的空間復雜度分析。

對算法占用存儲空間的分析類似于時間復雜度。估計漸近空間復雜度，稱為空間復雜度。由于問題中原始數據所占用的空間與算法無關，故一般考慮空間復雜度時只估算算法中所需增添的輔助空間。例如，例1-5中除原始數據外，只用了兩個變量x和i的輔助空間。因為與問題的規模n無關，所以空間復雜度S(n)=O(1)。

在一般情況下，算法的時間和空間開銷是一對矛盾。要想空間比較節約，往往時間消耗就大，反之亦然。具體在一個問題中到底注重哪一方面，這要看實際的需要和可能而定。在本書中，著重考慮時間因素，而假設內存足夠大。因為在求解實際問題中，當輸入量急劇增加時，如果沒有高效率的算法，單純依靠提高計算機的速度，有時是無法達到要求的。

注：O 是數學符號，它的定義是，若 f(n)是正整數 n 的一個函數，則 T(n)=O(f(n))表示存在一個正的常數 M，使得當 n≥n0時都滿足|T(n)|≤ M|f(n)|，即表明算法所需執行時間是f(n)的常數倍。如例1-6中，當n≥1時，T(n)≤3n，即n0=1，M=3，f(n)=n。