1.3 算法概述

1.3.1 什么是算法

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

一個算法應該具備以下5個重要特性。

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

（2）確定性：算法中每一條指令都必須具有確切的含義，不能有二義性，并且，在任何條件下，算法的任意一條執行路徑都是惟一的，即對于相同的輸入所得的輸出相同。

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

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

（5）輸出：一個算法有零個或多個輸出，這些輸出是同輸入有著某些特定關系的量。

說明：算法和程序是不同的，程序是指使用某種計算機語言對一個算法的具體實現，即程序描述了具體怎么做，而算法側重于描述解決問題的方法。

在使用計算機求解實際中的問題時，不僅要選擇合適的數據結構，還要有好的算法，那么應該如何評價一個算法的好壞呢？通常按以下指標來衡量。

（1）正確性：要求算法能夠正確地執行，并滿足預先設定的功能和性能要求，大致分為以下4個層次。

①程序不含語法錯誤。

②程序對于幾組輸入數據，能夠得出滿足要求的結果。

③程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數據，能夠得出滿足要求的結果。

④程序對于一切合法的輸入數據，都能夠得出滿足要求的結果。

（2）可讀性：算法主要是為了給人們閱讀和交流的，其次才是在計算機上執行。一個算法的可讀性好才便于人們理解，人們才有可能對程序進行調試，并從中找出錯誤。接下來給出幾個在程序編寫上提高可讀性的方法。

①注釋：給程序添加注釋，不僅有利于程序設計者自己閱讀和查錯，也為后續維護人員理解該程序帶來方便。

②變量命名：較復雜的程序通常會涉及較多的變量命名，此時應合理設計變量的名字，從而給后續使用該變量帶來方便。

（3）健壯性：當輸入的數據不合法或運行環境改變時，算法能恰當地做出反應或進行處理，而不是產生莫名其妙的輸出結果。

（4）時間復雜度：對一個算法執行效率的度量。

（5）空間復雜度：是指一個算法在執行過程中所占用的存儲空間的度量。

1.3.2 算法的時間復雜度

算法的執行時間是通過依據該算法編寫的程序在計算機上執行時所需要的時間來計算的，通常有以下兩種方法。

（1）事后統計法：因為很多的計算機有精確的計時功能，所以可以在計算機中執行依據某一算法編寫的程序，從而計算出該算法的執行時間。但此時間又與所使用的編程語言，以及計算機的硬件和軟件等環境因素有關，有時容易掩蓋算法本身的優劣，因此很少使用。

（2）事前分析估算法：通常用高級程序設計語言編寫的程序在計算機上運行時消耗的時間取決于下列因素。

①算法選用何種策略。

②問題的規模。

③所使用的程序設計語言，就同一個算法而言，用級別越高的語言實現，其執行的效率越低。

④編譯程序所產生的機器代碼的質量。

⑤機器執行指令的速度。

由上述因素可以看出，采用絕對的時間單位來衡量一個算法的效率是不合理的，因此我們撇開所使用的編程語言、計算機的硬件和軟件等環境因素，僅考慮算法本身效率的高低。即認為某一算法的執行時間只依賴于問題的規模，或者說是問題規模的函數。在后面的介紹中，也主要采用事前分析估算法來分析算法的時間性能。

一個算法通常是由控制結構（順序、分支和循環3種）和原操作（指固有數據類型的操作）構成的。例如在算法1-1中第6、8和9行代碼對應的操作就是原操作。

因此算法的執行時間取決于控制結構和原操作的綜合效果。為了便于算法執行時間的計算，我們從算法中選取一種對于所研究的問題來說是基本操作的原操作，并以該操作重復執行的次數來計算其執行時間。

假設問題規模為n，對應的函數關系記為T(n)，則算法的執行時間大致等于執行基本操作所需的時間×T(n)。通常執行基本操作所需的時間是某個確定的值，因此T(n)與算法的執行時間成正比，那么我們通過比較不同算法的T(n)大小，就可以得出不同算法的優劣。接下來我們以算法1-2為例，給出求解T(n)的過程。

上述第5～7行代碼是該算法的可執行語句，第5行代碼中的i從0變化到n，因此重復次數是n+1次，但對應的循環體只執行n次；同理第6行代碼本身重復的次數也為n+1，對應的循環體只執行n次，但由于其嵌套在第5行代碼內，因此第6行代碼共重復n(n+1)次。同理第7行代碼重復的次數為n2。

綜上所述，算法1-2的T(n)可用下式表示。

T(n)=n+1+n(n+1)+n2=2n2+2n+1

由于上述對算法執行時間的計算并不是該算法執行的絕對時間，因此通常進一步將算法的執行時間用T(n)的數量級來表示，記作T(n)=O(f(n))（其中O是數量級Order的縮寫）。具體含義是存在著正常量和N（N為一個足夠大的正整數），使得成立，由該等式可以看出當n足夠大時，T(n)和f(n)的增長率是相同的，因此我們將O(f(n))稱為算法的漸進時間復雜度，簡稱算法的時間復雜度。

與T(n)對應的f(n)可能有多個，通常只求出T(n)的最高階，而忽略其低階項、系數及常數項。如對于T(n)=n+1+n(n+1)+n2=2n2+2n+1=O(n2)，即算法1-2的時間復雜度為O(n2)。

通常，若算法中不存在循環，則算法時間復雜度為常量；若算法中僅存在單重循環，則決定算法時間復雜度的基本操作是算法中該循環中語句對應的基本操作；若算法中存在多重循環，則決定算法時間復雜度的基本操作是算法中循環嵌套層數最多的語句對應的基本操作重復的次數。

（1）算法中無循環。算法1-3中無循環，因此該算法的時間復雜度為O(1)，稱為常量階。

（2）算法中含有一個單重循環。算法1-4中含有一個單重循環，變量i從0變化到n，第6行中的基本操作執行了n次，因此該算法的時間復雜度為O(n)，稱為線性階。

（3）算法中含有多重循環。這里以雙重循環為例。算法1-5中有雙重循環，外循環變量i從0變化到n，內循環變量j從0變化到n，因此第7行中的基本操作執行了n2次，即該算法的時間復雜度為O(n2)，稱為平方階。

此外，對于有輸入的算法，其時間復雜度還與輸入數據集（一個或多個輸入）有關。因為對于不同的輸入數據集，算法的基本操作重復的次數可能不一樣，即算法的時間復雜度可能也不一樣。

對于一個有輸入的算法，在輸入不同的數據集情況下，若其基本操作重復的次數最少，則我們將此時對應的時間復雜度稱為算法的最好時間復雜度，反之，若基本操作重復的次數最多，則稱為算法的最壞時間復雜度。在實際應用時，我們考慮在等概率的前提下算法的平均時間復雜度。

接下來結合具體實例給出算法的最好、最壞及平均時間復雜度的分析和計算過程。

【例1-1】列表List中含有n個數據，算法1-6用于求List的前i（1≤i≤n）個數據中最大的數據。請分析該算法的最好、最壞和平均時間復雜度。

前i個數據為List[0,i-1]，要返回其中最大的數據，需要進行i-1次比較。因為1≤i≤n，所以共有n種情況，在每種情況出現的概率相等（即均為1/n）的前提下，可知

因此該算法的平均時間復雜度為O(n)。

當需要求前1個數據的最大值即i=1時，不需要執行第9行的基本操作，此時對應算法的最好時間復雜度為O(1)。

當需要求前n個數據的最大值即i=n時，需要執行n-1次第9行的基本操作，此時對應算法的最壞時間復雜度為O(n)。

1.3.3 算法的空間復雜度

與算法的時間復雜度類似，算法的空間復雜度一般也認為是問題規模n的函數，并以數量級的形式給出，記作

S(n)=O(g(n))

依據某算法編寫的程序在計算機運行時所占用的存儲空間包括以下部分：輸入數據所占用的存儲空間，程序本身所占用的存儲空間和臨時變量所占用的存儲空間。在對算法的空間復雜度進行研究時，只分析臨時變量所占用的存儲空間。例如，在算法1-7中，不計形參List所占用的空間，而只是計算臨時變量i和sum所占用的存儲空間，因此該算法的空間復雜度為O(1)。

為什么在對算法的空間復雜度進行分析時，只考慮臨時變量所占用的存儲空間而不考慮形參占用的存儲空間呢？我們來看算法1-8。

算法1-8為列表List分配存儲空間，而在第6行代碼中，我們可以看到其調用了算法1-7中的Sum()函數。若在算法1-7中，我們再次考慮形參List占用的存儲空間，則就重復計算了其占用的存儲空間。

由上述實例可知，在對算法的空間復雜度進行分析時，只需考慮臨時變量所占用的存儲空間而不用考慮形參占用的存儲空間。