1.2 算法

1.2.1 什么是算法

1.算法定義

曾獲圖靈獎的著名計算科學家D.knuth對算法做過一個為學術界廣泛接受的描述性的定義。一個算法（algorithm）是一個有窮規則的集合，其規則確定了一個解決某一特定類型問題的操作序列。算法的規則必須滿足以下5個特性。

? 有窮性：對于任意一組合法的輸入值，算法在執行有窮步驟之后一定能結束。即算法的操作步驟為有限個，且每步都能在有限時間內完成。

? 確定性：對于每種情況下所應執行的操作，在算法中都有確切的規定，使算法的執行者或閱讀者都能明確其含義及如何執行。并且，在任何條件下，算法都只有一條執行路徑。

? 可行性：算法中的所有操作都必須足夠基本，都可以通過已經實現的基本操作運算有限次實現之。

? 有輸入：算法有零個或多個輸入數據。輸入數據是算法的加工對象，既可以由算法指定，也可以在算法執行過程中通過輸入得到。

? 有輸出：算法有一個或多個輸出數據。輸出數據是一組與輸入有確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能。

2.算法設計目標

算法設計應滿足以下5個目標。

? 正確性：算法應確切地滿足應用問題的需求，這是算法設計的基本目標。

? 健壯性：即使輸入數據不合適，算法也能做出適當處理，不會導致不可控結果。

? 高時間效率：算法的執行時間越短，時間效率越高。

? 高空間效率：算法執行時占用的存儲空間越少，空間效率越高。

? 可讀性：算法表達思路清晰，簡潔明了，易于理解。

如果一個操作有多個算法，顯然應該選擇執行時間短和存儲空間占用少的算法。但是，執行時間短和存儲空間占用少有時是矛盾的，往往不可兼得，此時算法的時間效率通常是首要考慮因素。

3.算法描述

可以用自然語言描述算法。例如，查找是數據結構的一種基本操作，有多種查找算法可實現查找功能，最簡單的是順序查找算法。在圖1.5所示的學生信息表中，以“姓名”為關鍵字進行順序查找，從表的一端開始，依次將每位學生的姓名與給定值進行比較，若有相等者，則查找成功，查找操作結束；否則繼續比較，直到比較完所有元素，若仍未有相等者，則查找不成功，給出結果信息。

也可以用偽碼描述算法。采用偽碼描述順序查找的算法如下：

            元素search（關鍵字key）
            {
                e= 數據序列的第一個元素;
                whiIe（數據序列未結束 &&e的關鍵字不是key）
                    e= 數據序列的下一個元素;
                返回查找到的元素或查找不成功標記;
            }

用自然語言或偽碼描述算法能夠抽象地描述算法設計思想，但是計算機無法執行。因此，數據結構和算法實現需要借助程序設計語言，將算法表達成基于一種程序設計語言的可執行程序。

4.算法與數據結構

算法建立數據結構之上，對數據結構的操作需要用算法來描述。例如，線性表有遍歷、插入、刪除、查找、排序等操作；樹有遍歷、查找、插入、刪除等操作。通過研究算法，我們能夠更深刻地理解數據結構的操作。

算法設計依賴于數據的邏輯結構，算法實現依賴于數據的存儲結構。例如，線性表的插入和刪除操作，由于采用順序存儲結構，數據元素是相鄰存儲的，所以插入前、刪除后都必須移動一些元素；采用鏈式存儲結構，插入或刪除一個元素只需改變相關結點的鏈接關系，不需移動元素。順序表和鏈表的插入操作如圖1.6所示。

實現一種抽象數據類型，需要選擇合適的存儲結構，使得以下兩方面的綜合性能最佳：數據操作所花費的時間短，占用的存儲空間少。對線性表而言，當不需要頻繁進行插入和刪除操作時，可采用順序存儲結構；當插入和刪除操作很頻繁時，可采用鏈式存儲結構。

1.2.2 算法分析

衡量算法性能的標準主要有算法的時間效率和空間效率。

1.度量算法的時間效率

算法的執行時間是算法中涉及的存、取、轉移、加、減等各種基本運算的執行時間之和。算法的執行時間與參加運算的數據量有關，很難事先計算得到。

算法的時間效率是指算法的執行時間隨問題規模的增長而增長的趨勢，通常采用時間復雜度來度量。當問題的規模以某種單位從1增加到n時，解決這個問題的算法在執行時所耗費的時間也以某種單位由1增加到T（n），稱此算法的時間復雜度（time complexity）為T（n）。當n增大時，T（n）也隨之增大。

在算法的漸進分析中，用大O表示法作為算法時間復雜度的漸進度量值。大O表示法指，當且僅當存在正整數c和n0，使得T（n）≤cf（n）對所有的n≥n0成立時，則稱該算法的時間增長率與f（n）的增長率相同，記為T（n）=O（f（n））。

若算法的執行時間是常數級，不依賴于數據量n的大小，則時間復雜度為O（1）；若算法的執行時間是n的線性關系，則時間復雜度為O（n）；同理，對數級、平方級、立方級、指數級的時間復雜度分別為 O（log2 n）、O（n2）、O（n3）、O（2n）。這些函數按數量級遞增排列具有下列關系：O（1）<O（log2 n）<O（n2）<O（n3）<O（2n）。

時間復雜度O（f（n））隨數據量n變化情況的比較如表1-2所示。

如何估算算法的時間復雜度？一個算法通常由一個控制結構和若干基本操作組成，則

算法的執行時間 =基本操作（i）的執行次數×基本操作（i）的執行時間

由于算法的時間復雜度表示的是算法執行時間的增長率而非絕對時間，因此可以忽略一些次要因素。設基本操作的執行時間是常量級O（1），則算法的執行時間是基本操作執行次數之和，以此作為估算算法時間復雜度的依據，可表示算法本身的時間效率。

【例1.1算法的時間復雜度分析。

本例討論各種算法結構的時間復雜度。分析一個算法中基本語句的執行次數，可求出該算法的時間復雜度。

① 一個簡單語句的時間復雜度為O（1）。

            int count=0;

② 執行n次的循環語句，時間復雜度為O（n）。

            int n=8, count=0;
            for（int i=1; i<=n; i++）
              count++;

③ 時間復雜度為O（log2 n）的循環語句。

            int n=8, count=0;
            for（int i=1; i<=n; i＊=2）
                count++;

i取值為1、2、4、8，循環執行1+log2n次，故循環語句的時間復雜度為O（log2n）。

④ 時間復雜度為O（n2）的二重循環。

            int n=8, count=0;
            for（int i=1; i<=n; i++）
                for（int j=1; j<=n; j++）
                  count++;

外層循環執行n次，每執行一次外層循環時，內層循環執行n次。所以，二重循環中的循環體語句執行n×n次，時間復雜度為O（n2）。如果

            int n=8, count=0;
            for（int i=1; i<=n; i++）
                for（int j=1; j<=i; j++）
                  count++;

外層循環執行n次，每執行一次外層循環時，內層循環執行i次。此時，二重循環的執行次數為，時間復雜度仍為O（n2）。

⑤ 時間復雜度為O（n×log2 n）的二重循環。

            int n=8, count=0;
            for（int i=1; i<=n; i＊=2）
                for（int j=1; j<=n; j++）
                  count++;

外層循環執行1+log2 n次，內層循環執行次數恒為n，總循環次數為n×（1+log2 n），時間復雜度為O（n×log2 n）。

⑥ 時間復雜度為O（n）的二重循環。

            int n=8, count=0;
            for（int i=1; i<=n; i＊=2）
                for（int j=1; j<=i; j++）
                  count++;

外層循環執行1+log2n次，i取值為1，2，4，…，內層循環執行i次，i隨著外層循環的增加而成倍遞增?？傃h次數為，時間復雜度為O（n）。

2.度量算法的空間效率

執行一個算法所需要的存儲空間包括三部分：輸入數據占用的存儲空間、程序指令占用的存儲空間、輔助變量占用的存儲空間。其中，輸入數據和程序指令所占用的存儲空間與算法無關，因此輔助變量占用的存儲空間就成為度量算法空間效率的依據。

當問題的規模以某種單位從1增加到n時，解決這個問題的算法在執行時所占用的存儲空間也以某種單位由1增加到S（n），則稱此算法的空間復雜度（space complexity）為S（n）。當n增大時，S（n）也隨之增大?？臻g復雜度用大O表示法記為S（n）=O（f（n）），表示該算法的空間增長率與f（n）的增長率相同。

1.2.3 算法設計

表達數據結構和算法的設計思想不依賴于程序設計語言，實現數據結構和算法則依賴于程序設計語言。不僅如此，描述數據結構所采用的思想和方法還必須隨著軟件方法及程序設計語言的不斷發展而發展。面向對象程序設計方法是目前軟件設計的主流方法，C++語言是目前應用廣泛的一種面向對象程序設計語言，具備了表達數據結構和算法的基本要素。

算法設計是軟件設計的基礎。“數據結構”課程是一門理論和實踐緊密結合的課程，既要透徹理解抽象的理論知識，又要鍛煉程序設計能力。因此，依托一種功能強大的程序設計語言，充分表達和實現復雜的設計思想，是提高程序設計能力的一種有效手段。

本書依托功能強大的C++語言，不僅能夠描述數據結構和實現算法，而且以面向對象程序設計思想貫穿始終，體現了軟件模塊化、可重用的設計思想。以C++語言的類實現各種數據結構參見后續章節。以下通過討論交換、查找、排序等典型問題，說明使用C++語言的函數、指針、引用、模板等的常見問題，說明算法的必要性、算法表達以及時間復雜度和空間復雜度分析。

【例1.2交換兩個變量值的問題討論。

在應用程序設計時，交換兩個變量值是經常遇到的一個問題，這個問題的關鍵是一個函數如何返回兩個變量值。在C++語言中可將函數參數聲明為指針（*）或引用（&）類型實現。

本例的目的是說明表達設計思想、實現特定功能所需要使用的函數、指針、引用、模板等C++語言基礎。

① 函數參數聲明為基本數據類型

如果swap（?。┖瘮德暶魅缦拢?/p>

            void swap（int x,int y）                      //不能實現交換
            {
                int temp=x;
                x=y;
                y=temp;
            }

調用語句如下：

            int i=1,j=2;
            swap（i,j）;

調用swap（i, j）函數時，將實際參數i、j的值傳遞給形式參數x、y；在函數體中交換了兩個局部變量x、y的值，但交換結果并未影響實際參數i、j，如圖1.7所示。因此，上述swap（?。┖瘮挡荒軐崿F交換兩個變量值的功能。

② 函數參數聲明為指針類型

將函數參數聲明為指針類型，聲明如下：

            void swap（int＊x,int＊y）                     //指針參數得到實際參數的地址
            {
                int temp=＊x;
                ＊x=＊y;
                ＊y=temp;
            }

調用語句如下：

            swap（&i,&j）;

swap（&i, &j）函數調用時，傳遞給形式參數x、y的是實際參數的地址&i、&j，此后對*x、*y的操作就如同對i、j的操作，如圖1.8所示。因此，上述swap（?。┖瘮的軌驅崿F交換兩個變量值的功能。

③ 函數參數聲明為引用類型

與指針類型的函數參數相似，在C++語言中，也可將函數參數聲明為引用類型，對形式參數操作就是對實際參數操作。聲明如下：

            void swap（int&x,int&y）                //參數為引用，對x、y操作就是對實際參數操作
            {
                int temp = x;
                x = y;
                y = temp;
            }

調用語句如下（執行過程同圖1.8）：

            swap（i, j）;

④ 函數模板

采用函數模板交換任意數據類型的兩個變量，聲明如下：

            tempIate <cIass T>
            void swap（T&x,T&y）                 //T指定變量類型
            {
                T temp = x;
                x = y;
                y = temp;
            }

調用語句如下：

            swap（i, j）;

⑤ 交換一個數組中的兩個元素值

當數組作為函數參數時，傳遞的是數組首地址。因此，以下函數能夠交換一個數組中的兩個元素。

            tempIate <cIass T>
            void swap（T tabIe[],int n,int i,int j）        //交換tabIe[i]、tabIe[j]值，n指定數組元素個數
            {
                if（i>=0&&i<n&&j>=0&&j<n&&i!=j）            //避免下標越界
                {   T temp=tabIe[i];
                  tabIe[i] = tabIe[j];
                  tabIe[j] = temp;
                }
            }

執行過程如圖1.9所示。

在swap（　）函數中，使用3條語句實現交換功能，時間復雜度是O（1）；使用一個局部變量temp作為額外存儲空間，空間復雜度是O（1）。

【思考題】以下交換兩個變量值的swap（?。┖瘮德暶魇欠裾_？為什么？

            void swap（int ＊x, int ＊y）
            {
                int ＊temp = x;
                x = y;
                y = temp;
            }

【例1.3求兩個整數的最大公約數。

本例以求最大公約數為例，說明算法的必要性。

① 質因數分解法

數學方法求兩個整數的最大公約數是，分別將兩個整數分解成若干質因數的乘積，再比較兩者的公約數，從中選擇最大者。例如，已知26460=22×33×5×72，12375=32×53×11，則26460與12375的最大公約數為32×5=45。

質因數分解法基于算術基本定理，解決了公約數和公倍數問題。但它的理論成果很難應用于實際計算中，因為大數的質因數很難分解。

② 更相減損術

在中國古代數學經典著作《九章算術》的方田章中，給出最大公約數的“更相減損”解法，“以少減多，更相減損，求其等也，以等數約之。等數約之，即除也，其所以相減者皆等數之重疊，故以等數約之?！逼渲械葦导粗竷蓴档淖畲蠊s數。如求91和49的最大公約數，其逐步減損的步驟為：（91, 49）=（42, 49）=（42, 7）=7。

該法“寓理于算，不證自明”，不僅給出解題步驟，也說明了解題道理。

③ 歐幾里得（Euclid）的輾轉相除法

記gcd（a, b）為兩個整數a和b的最大公約數，gcd（a, b）具有如下性質：

gcd（a,b）=gcd（b,a）

gcd（a,b）=gcd（-a,b）

gcd（a,0）=|a|

gcd（a,b）=gcd（b,a%b）, 0≤ a %b ＜b

例如，gcd（91,49）=gcd（49,42）=gcd（42,7）=gcd（7,0）=7。實際上，輾轉相除法就是現代版的更相減損術。

實現輾轉相除法的C++語言描述的gcd（a,b）函數如下：

            int gcd（int a,int b）                     //返回a與b的最大公約數
            {
                whiIe（b!=0）
                {   int k=a%b;
                  a = b;
                  b = k;
                }
                return a;
            }

求整數26460和12375的最大公約數，計算過程如下：

            gcd（26460,12375）=gcd（12375,1710）=gcd（1710,405）=gcd（405,90）=gcd（90,45）=gcd（45,0）=45

求三個整數a、b、c的最大公約數的調用語句如下：

            gcd（gcd（a, b）, c）

【例1.4】數組的順序查找算法。

本例實現1.2.1節中描述的順序查找算法，采用數組存儲數據序列。根據數據序列是否排序的前提條件，采取的順序查找算法有所不同。

① 順序查找算法

1.2.1節中描述的是數據序列沒有排序的順序查找算法。以下程序采用隨機數序列作為未排序的數據序列，進行順序查找。

            #incIude <iostream.h>
            #incIude<stdIib.h>                      //其中定義隨機數函數rand（?。?
            void random（int tabIe[],int n）        //將數組元素填充為非0隨機數，n指定數組長度
            {
                int i=0;
                whiIe（i<n）
                {   int vaIue=rand（　）% 100;      //隨機數范圍是0～99
                  if（vaIue!=0）
                      tabIe[i++] = vaIue;
                }
            }
            tempIate <cIass T>
            void print（T tabIe[],int n）           //輸出數組的n個元素，函數體省略

            tempIate <cIass T>
            int index（T tabIe[],int n,T vaIue）    //在數組中查找值vaIue
            {                                       //若查找成功返回元素下標，否則返回-1
                for（int i=0; i<n; i++）
                {
                  cout<<tabIe[i]<<"?";              //輸出中間結果，可省略
                  if（tabIe[i]==vaIue）
                      return i;
                }
                return -1;
            }
            int main（　）
            {
                const int N=10;
                int tabIe[N]={0};
                random（tabIe,N）;
                cout<<"隨機數序列：";
                print（tabIe, N）;
                int key=50;
                cout<<"順序查找 "<<key<<"，"<<（（index（tabIe,N,key）==-1）?"不"：""）<<"成功\n";
                return 0;
            }

程序運行結果如下：

            隨機數序列：41  67  34  69  24  78  58  62  64  5
            41?67?34?69?24?78?58?62?64?5? 順序查找 50, 不成功

順序查找的比較次數取決于元素位置。已知數據序列的元素個數為 n，設各元素的查找概率相等，若查找成功，第i（0 i＜n）個元素的比較次數為i+1，平均比較次數為n/2；若查找不成功，則比較n次。因此，順序查找的時間復雜度為O（n）。算法分析詳見第8章。

② 已排序數據序列的順序查找算法

如果數組元素已按升序排序，采用順序查找從數組的第一個元素開始比較，只要遇到一個元素大于給定值，則能夠確定查找不成功，不需要再比較其他元素。修改的index（?。┖瘮狄娎?.5。

在已排序的數據序列中進行順序查找，查找成功和查找不成功的平均比較次數都是n/2。已排序數組可采用折半查找算法，效率較高，詳見第8章。

順序查找是其他一些操作的基礎，如求數組的最大值或最小值、替換指定元素值等。

【例1.5】排序算法及其必要性。

本例說明排序算法的必要性，描述直接插入排序和直接選擇排序思路，給出直接插入排序算法實現。

① 排序算法的必要性

已知經過一次比較可判斷兩個數的大小，據此可實現兩個數排序輸出。函數如下：

            void sort（int a,int b）                       //兩個整數按升序排序輸出
            {
                if（a<b）
                  cout<<a<<","<<b<<endI;
                eIse
                  cout<<b<<","<<a<<endI;
            }

已知3個整數有6種排列，將3個整數按升序排序輸出的函數如下：

            void sort（int a,int b,int c）                 //三個整數按升序排序輸出
            {
                if（a<b）
                  if（b<c）
                      cout<<a<<","<<b<<","<<c<<endI;
                  eIse if（a<c）
                          cout<<a<<","<<c<<","<<b<<endI;
                      eIse
                          cout<<c<<","<<a<<","<<b<<endI;
                eIse if（a<c）
                      cout<<b<<","<<a<<","<<c<<endI;
                  eIse if（c<b）
                          cout<<c<<","<<b<<","<<a<<endI;
                      eIse
                          cout<<b<<","<<c<<","<<a<<endI;
            }

這種方法考慮了所有可能情況，稱為窮舉法，也稱為蠻力法。顯然，它不能解決n（n>3）個元素的排序問題，不具有廣泛性就不能被稱為一種算法。因此，必須提供通用的排序算法解決n個元素的排序問題。

② 直接插入排序

將一個元素value插入到一個已排序數組中，使得插入后該數組元素仍然是排序的。首先需要使用順序查找算法確定元素value的插入位置i，再將i位置之后的若干元素向后移動，空出i位置，最后將元素value存放在數組的i位置。

在數據序列{24, 34, 41, 67, 69, 78}中，插入元素58的算法描述如圖1.10所示。

依次將多個元素插入到指定數組中，則實現直接插入排序（straight insertion sort）。

程序如下。

            #incIude <iostream.h>
            #incIude <stdIib.h>
            tempIate <cIass T>
            void print（T tabIe[],int n）                    //輸出數組的n個元素，函數體省略

            tempIate <cIass T>
            int index（T tabIe[],int n,T vaIue）             //在已按升序排序的數組中順序查找vaIue
            {                                                //若查找成功返回元素下標，否則返回-1
                for（int i=0;i<n&&tabIe[i]<=vaIue;i++）
                {   cout<<tabIe[i]<<"?";                     //輸出中間結果，可省略
                  if（tabIe[i]==vaIue）
                      return i;
                }
                return-1;
            }

            tempIate<cIass T>
            void insert（T tabIe[],int n,T vaIue）           //在數組中插入vaIue，n指定數組元素個數
            {
                int i=0;
                whiIe（i<n&&vaIue>=tabIe[i]）                //順序查找vaIue的插入位置
                  i++;
                for（int j=n-1;j>=i;j--）
                  tabIe[j+1]=tabIe[j];                       //元素向后移動
                tabIe[i]=vaIue;                              //i是vaIue的插入位置
            }
            int main（　）
            {
                const int N=8;
                int tabIe[N]={0};
                int i=0;
                whiIe（i<N）                                 //產生N個非0的隨機數
                {   int vaIue=rand（?。? 100;               //隨機數范圍是0～99
                  if（vaIue!=0）
                  {   cout<<"插入"<<vaIue<<",\t";
                      insert（tabIe,i,vaIue）;               //按升序插入到數組中
                      i++;
                      print（tabIe,i）;
                  }
                }
                int key=50;
                cout<<"順序查找 "<<key<<"，"<<（（index（tabIe,N,key）==-1）?"不"：""）<<"成功\n";
                return 0;
            }

程序運行結果如下：

            插入41,           41
            插入67,           41  67
            插入34,           34  41  67
            插入69,           34  41  67  69
            插入24,           24  34  41  67  69
            插入78,           24  34  41  67  69  78
            插入58,           24  34  41  58  67  69  78
            插入62,           24  34  41  58  62  67  69  78
            0?24?34?41 順序查找 50，不成功

insert（?。┖瘮得坎迦胍粋€元素，平均比較次數為n/2，平均移動次數為n/2，因此插入一個元素的時間復雜度為O（n），直接插入排序的時間復雜度為O（n2）。詳細分析見第9章。

③ 直接選擇排序

直接選擇排序的基本思想是：第一趟從n個元素的數據序列中選出關鍵字最?。ɑ蜃畲螅┑脑夭⒔粨Q到最前（或最后）位置，下一趟再從n-1個元素中選出最小（大）的元素并放到次前（后）位置，依次類推，經過n-1趟完成排序。詳見第9章。

④ 任意數據類型T需要重載某些運算符

查找和排序操作都需要經過若干次比較來獲得結果，比較由6種關系運算（==、!=、>、>=、<、<=）實現。但查找和排序操作所進行的關系運算是不同的，一般而言，查找操作需要比較兩個元素是否相等，采用關系運算==和!=；排序操作需要比較兩個元素的大小，采用關系運算>、>=、<、<=。

C++的基本數據類型定義了這6種關系運算；字符串（char*）的比較由string.h中的strcmp（?。┖瘮堤峁ㄒ娎?.1）；結構體類型和類沒有定義這6種關系運算，因此若采用函數模板表達查找或排序算法，T的實際數據類型必須提供所需的關系運算，即重載某些關系運算符（見第4章的例4.4）。

同理，例1.4和本例的print（T table[], int n）函數使用以下語句輸出數組指定元素：

            cout<<tabIe[i]<<"  ";

該語句能夠正常運行的前提是，T的實際數據類型提供輸出流運算。

重載輸出流運算符<<見第2章的例2.2。