1.3 算法和算法的分析

1.3.1 算法及算法的描述

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

（1）有窮性。一個算法必須總是（對任何合法的輸入值）在執行有窮步之后結束，且每一步都可在有窮時間內完成。

（2）確定性。算法中每一條指令必須有確切的含義，不能產生二義性。在任何條件下，算法只有唯一的一條執行路徑，即對于相同的輸入只能得出相同的輸出。

（3）可行性。一個算法是可行的，即算法中描述的操作可通過已經實現的基本運算執行有限次來實現。

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

（5）輸出。一個算法有一個或多個輸出。這些輸出是與輸入有著一定關系的量。

《數據結構》中所討論的算法，可用不同的方式進行描述，常用的有類Pascal、類C、類C++、類Java程序設計語言，本教材以類C語言為描述工具。每一算法可用一個或多個簡化了的C語言（類C）函數進行描述，簡化是針對高級語言的語法細節所做的，如對函數內部的局部變量可不作聲明而直接使用，交換兩個變量x、y的值，不使用3條賦值語句，而僅簡記為一條語句x←→y；再如對結構體變量可以整體賦值，等等。需要注意的是，《數據結構》中的算法，因為用類C描述，所以不等同于C語言程序，若要上機運行某一算法，則必須將其完善為C語言程序。即增加main()函數，main()函數中增添實現算法的函數調用語句，在實現算法的函數中補充、完善語法細節。

1.3.2 算法設計的要求

1.正確性

正確性的含義是算法對于一切合法的輸入數據都能夠得出滿足規格說明要求的結果，事實上要驗證算法的正確性是極為困難的，因為通常情況下合法的輸入數據量太大，用窮舉法逐一驗證是不現實的。所謂的算法正確性是指算法達到了測試要求。

2.可讀性

可讀性是指人對算法閱讀理解的難易程度，可讀性高的算法便于人之間的交流，有利于算法的調試與修改。

3.健壯性

對于非法的輸入數據，算法能給出相應的響應，而不是產生不可預料的后果。

4.效率與低存儲量需求

效率指的是算法的執行時間。對于解決同一問題的多個算法，執行時間短的算法效率高。存儲量需求指算法執行過程中所需要的最大存儲空間。效率與低存儲量需求兩者都與問題的規模有關，求100個人的平均分與求1000個人的平均分顯然不同。

1.3.3 算法的分析

1.算法效率的度量

算法執行的時間是其對應的程序在計算機上運行所消耗的時間。程序在計算機上運行所需時間與下列因素有關：

（1）算法本身選用的策略；

（2）書寫程序的語言；

（3）編譯產生的機器代碼質量；

（4）機器執行指令的速度；

（5）問題的規模。

度量一個算法的效率應拋開具體機器的軟、硬件環境，而書寫程序的語言、編譯產生的機器代碼質量、機器執行指令的速度都屬于軟、硬件環境。對于一個特定算法只考慮算法本身的效率，而算法自身的執行效率是問題規模的函數。對同一個問題，選用不同的策略就對應不同的算法，不同的算法對應有各自的問題規模函數，根據這些函數就可以比較（解決同一個問題的）不同算法的優劣。

2.算法的時間復雜度

一個算法的執行時間大致上等于其所有語句執行時間的總和，語句的執行時間是指該條語句的執行次數和執行一次所需時間的乘積。語句執行一次實際所需的具體時間是與機器的軟、硬件環境（機器速度、編譯程序質量和輸入數據等）密切相關的，與算法設計的好壞無關。所以，可以用算法中語句的執行次數來度量一個算法的效率。

首先定義算法中一條語句的語句頻度，語句頻度是指語句在一個算法中重復執行的次數。以下給出了兩個n×n階矩陣相乘算法中的各條語句，以及每條語句的語句頻度。

語句       語句頻度
for (i=0;i<n;i++)     n+1
     for (j=0;j<n;j++)     n(n+1)
         {  c[i][j]=0;       n2
            for (k=0;k<n;k++)   n2(n+1)
                c[i][j]=c[i][j]+a[i][k]*b[k][j];n3
         }

算法中所有語句的總執行次數為Tn=2n3+3n2+2n+1，從中可以看出，語句總的執行次數是問題的規模（矩陣的階）n的函數f(n)（Tn=f(n)）。進一步簡化，可用Tn表達式中n的最高次冪，即最高次冪項忽略其系數來度量算法執行時間的數量級，稱為算法的時間復雜度，記做：

T(n)=O(f(n))

以上算法的時間復雜度為T(n)=O(n3)。

算法中所有語句的總執行次數Tn是問題規模n的函數，即Tn=f(n)，其中n的最高次冪項與算法中稱為原操作的語句的語句頻度對應，原操作是實現算法基本運算的操作，上面算法中的原操作是c[i][j]=c[i][j]+a[i][k]*b[k][j]。一般情況下原操作由最深層循環內的語句實現。

T(n)隨n的增大而增大，增長得越慢，其算法的時間復雜度越低。下列3個程序段中分別給出了原操作count++的3個不同數量級的時間復雜度。

（1）count++；

其時間復雜度為O(1)，稱為常數階時間復雜度。

（2）for (i=1;i<=n;i++)

count++;

其時間復雜度為O(n)，是線性階時間復雜度。

（3）for (i=1;i<=n;i++)

for (j=1;j<=n;j++)
     count++;

其時間復雜度為O(n2)，是平方階時間復雜度。

又如以下兩個算法，它們所呈現的時間復雜度分別是O(log2n)和O(n×m)。

（1）i=1；

while (i<n)
    i=2*i;

（2）for (i=0;i<n;i++)

for (j=0;j<m;j++)
     a[i][j]=0;

3.最壞時間復雜度

算法中基本操作重復執行的次數還隨問題的輸入數據集的不同而不同，例如下面的冒泡排序算法：

void Bubble(int a[], int n)
/*對整數數組a中的n個元素從小到大排序*/
{  int i=0, j;
   int change ;
   do
   {  change=0 ;
      for (j=0;j<n-i-1;j++)
      if( a[j]>a[j+1])
          {
                  a[j]←→ a[j+1];/*交換序列中相鄰的兩個整數*/
                  change=1;
          }
       i=i+1 ;
   }while (i<n-1 && change )
}

在這個算法中，“交換序列中相鄰的兩個整數”（a[j]←→a[j+1]）為原操作。當a中初始序列為自小到大有序時，原操作的執行次數為0；當初始序列為自大到小有序時，原操作的執行次數為n(n-1)/2。對于這類算法時間復雜度的分析，一種解決的方法是計算它的平均值，即考慮它對所有可能輸入數據集的期望值，此時相應的時間復雜度為算法的平均時間復雜度。然而在很多情況下，算法的平均時間復雜度是難以確定的，通常的做法是討論算法在最壞情況下的時間復雜度。例如，冒泡排序在最壞情況下（初始序列為自大到小有序時）的時間復雜度就為T(n)=O(n2)。本教材中，如不進行特殊說明，所討論的各算法的時間復雜度均指最壞情況下的時間復雜度。

4.常見的時間復雜度

常見的時間復雜度有：O(1)常數階、O(n)線性階、O(n2)平方階、O(n3)立方階、O(2n)指數階、O(log2n)對數階和線性對數階O(nlog2n)。時間復雜度（從小到大排列）的比較如表1-2所示。

表1-2 常用的時間復雜度的比較

5.算法的空間復雜度

關于算法的存儲空間需求，類似于算法的時間復雜度，采用空間復雜度作為算法所需存儲空間的量度，記為

S(n)=O(f(n))

其中n為問題的規模。一般情況下，一個程序在機器上執行時，除了需要寄存程序本身所用的指令、常數、變量和輸入數據以外，還需要一些對數據進行操作的輔助存儲空間。其中對于輸入數據所占的具體存儲量只取決于問題本身，與算法無關，這樣只需要分析該算法在實現時所需要的輔助空間單元數就可以了。若算法執行時所需要的輔助空間相對于輸入數據量而言是個常數，則稱這個算法為原地工作，輔助空間為O(1)。如果所占輔助空間量依賴于特定的輸入，則除特別指明外，均按最壞情況來分析。

算法的執行時間和存儲空間的耗費是一對矛盾體，即算法執行的高效通常是以增加存儲空間為代價的，反之亦然。不過，就一般情況而言，常常以算法執行時間作為算法優劣的主要衡量指標。本教材對算法的空間復雜度不作進一步討論。