1.3 算法的基本概念

1.3.1 算法及其重要特性

1.什么是算法

算法（algorithm）被公認為是計算機科學的基石。通俗地講，算法是解決問題的方法?，F實生活中關于算法的實例不勝枚舉，如一道菜譜、一個安裝轉椅的操作指南等，再如四則運算法則、算盤的計算口訣等。嚴格地說，算法是對特定問題求解步驟的一種描述，是指令的有限序列，如圖1-15所示。此外，算法還必須滿足下列五個重要特性：

圖1-15 算法的概念

（1）輸入：一個算法有零或多個輸入（即算法可以沒有輸入），這些輸入通常取自某個特定的對象集合。

（2）輸出：一個算法有一或多個輸出（即算法必須要有輸出），通常輸出與輸入之間有著某種特定的關系。

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

（4）確定性：算法中的每一條指令必須有確切的含義，不存在二義性。并且，在任何條件下，對于相同的輸入只能得到相同的輸出。

（5）可行性：算法描述的操作可以通過已經實現的基本操作執行有限次來實現。

算法和程序不同。程序（program）是對一個算法使用某種程序設計語言的具體實現，原則上，算法可以用任何一種程序設計語言實現。算法的有窮性意味著不是所有的計算機程序都是算法。例如操作系統是一個在無限循環中執行的程序而不是一個算法，然而我們可以把操作系統的各個任務看成是一個單獨的問題，每一個問題由操作系統中的一個子程序通過特定的算法來實現，得到輸出結果后便終止。

2.什么是“好”算法

一個“好”算法首先要滿足算法的五個重要特性，此外還要具備下列特性：

（1）正確性：指算法能滿足具體問題的需求，即對于任何合法的輸入，算法都會得出正確的結果。

（2）健壯性：指算法對非法輸入的抵抗能力，即對于錯誤的輸入，算法應能識別并做出處理，而不是產生錯誤動作或陷入癱瘓。

（3）可理解性：指算法容易理解和實現。算法首先是為了人的閱讀和交流，其次是為了程序實現，因此，算法要易于人的理解、易于轉換為程序。晦澀難懂的算法可能隱藏一些不易發現的邏輯錯誤。

（4）抽象分級：算法一旦創建，必須由人來閱讀、理解、使用和修改它們。而研究發現，對大多數人來說，人的認識限度是7±2。如果算法涉及的想法太多，人就會糊涂，因此，必須用抽象分級來組織算法表達的思想。換言之，算法中的每一個邏輯步驟可以是一條簡單的指令，也可以是一個模塊，通過模塊調用完成相應功能。每個模塊表示一種抽象，模塊的內部描述了怎樣實現抽象，而模塊的名稱描述了模塊的功能。

（5）高效性：算法的效率包括時間效率和空間效率，時間效率顯示了算法運行得有多快；而空間效率則顯示了算法需要多少額外的存儲空間。不言而喻，一個“好”算法應該具有較短的執行時間并占用較少的輔助空間。

1.3.2 算法的描述方法

算法設計者在構思和設計了一個算法之后，必須清楚準確地將所設計的求解步驟記錄下來，即描述算法。常用的描述算法的方法有自然語言、流程圖、程序設計語言和偽代碼等。下面以歐幾里得算法為例進行介紹。

1.自然語言

用自然語言描述算法，最大的優點是容易理解，缺點是容易出現二義性，并且算法通常都很冗長。歐幾里得算法用自然語言描述如下：

步驟1：將m除以n得到余數r；

步驟2：若r等于0，則n為最大公約數，算法結束，否則執行步驟3；

步驟3：將n的值放在m中，將r的值放在n中，重新執行步驟1。

2.流程圖

用流程圖描述算法，優點是直觀易懂，缺點是嚴密性不如程序設計語言，靈活性不如自然語言。歐幾里得算法用流程圖描述如圖1-16所示。

圖1-16 用流程圖描述歐幾里得算法

在計算機應用早期，使用流程圖描述算法占有統治地位，但實踐證明，除了描述程序設計語言的語法規則和一些非常簡單的算法，這種描述方法使用起來非常不方便。

3.程序設計語言

用程序設計語言描述的算法能由計算機直接執行，而缺點是抽象性差，使算法設計者拘泥于描述算法的具體細節，忽略了“好”算法和正確邏輯的重要性，此外，還要求算法設計者掌握程序設計語言及其編程技巧。歐幾里得算法用C語言書寫的程序如下：

            #include＜stdio.h＞
            intCommonFactor（intm，intn）
            {
              intr=m% n；
              while（r！=0）
              {
                  m=n；
                  n=r；
                  r=m% n；
              }
              returnn；
            }
            intmain（）
            {
              printf（＂最大公約數是：%d/n＂，CommonFactor（35，25））；
              return0；
            }

4.偽代碼

偽代碼（pseudo-code）是介于自然語言和程序設計語言之間的一種方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。至于算法中自然語言的成分有多少，取決于算法的抽象級別。抽象級別高的偽代碼自然語言多一些，抽象級別低的偽代碼程序設計語言的語句多一些。歐幾里得算法用偽代碼描述如下：

上述偽代碼可以再具體一些，一般采用某種程序設計語言的一個核心子集。本書采用C語言的基本語法和控制結構，為了便于描述算法，對C語言做了若干擴充和修改，具體如下：

（1）用函數來描述算法，并且不用在主函數中調用函數；

（2）增加了C++語言的引用參數傳遞方式，在形參表中以符號“&”開始的參數即為引用參數；

（3）當算法出現異常時，使用語句“exit（-1）；”結束算法的執行并將狀態碼-1返回；

（4）不用包含頭文件，輸入/輸出語句可以省略格式控制符；

（5）局部變量可以不聲明；

（6）用符號“←→”表示交換兩個變量的值。

采用C語言的函數來描述算法，使得算法的描述簡明清晰，既不拘泥于C語言的實現細節，又容易轉換為C/C++程序。歐幾里得算法的C語言描述如下：

            intCommonFactor（intm，intn）
            {
              r=m% n；
              while（r！=0）
              {
                m=n；
                n=r；
                r=m% n；
              }
              returnn；
            }

偽代碼不是一種實際的編程語言，但在表達能力上類似于編程語言，同時極小化了描述算法的不必要的技術細節，是比較合適的描述算法的方法，被稱為“算法語言”或“第一語言”。