1.4　算法和算法分析

1.4.1　算法

算法是計算機科學中的基本概念，是對特定問題的求解步驟。算法須具有下列五個特征。

（1）輸入：一個算法有0個或多個輸入。

（2）輸出：一個算法產生一個或多個輸出，作為算法運算的結果。

（3）可行性：算法的每一個步驟都可以通過已經實現的基本運算來實現。

（4）確定性：算法的每一個步驟都必須有確切的含義，不會產生二義性。

（5）有窮性：算法必須能在執行有窮步之后終止。

算法的描述方式多種多樣，可以用自然語言、流程圖、程序設計語言或偽代碼來描述。為了方便讀者理解算法和上機驗證算法，本書采用自然語言描述算法思想，并使用C語言描述算法的實現。

衡量一個算法的優劣，主要有以下幾個基本標準。

（1）正確性

在合理的數據輸入下，算法能夠在有限的時間內產生滿足預先規定的功能和性能要求。

（2）可讀性

一個好的算法應當思路清晰、簡單明了。可讀性高的算法便于人們閱讀、理解和交流；晦澀難懂的算法容易隱藏錯誤，不易被發現和調試。

（3）健壯性

一個好的算法應在輸入不合法數據時，能做出適當處理，而不至于產生異常或是出現崩潰等嚴重后果。

（4）高效性

評價一個算法的效率主要包括時間和空間兩方面。好的算法應具備執行效率高和占用存儲空間少的特點。時間復雜度和空間復雜度是衡量算法效率的兩個重要指標。

1.4.2　算法的時間復雜度

算法執行時間需通過依據該算法編制的程序在計算機上運行時所消耗的時間來度量。算法的時間復雜度一般是指程序運行從開始到結束所需的時間。而度量一個程序的執行時間通常有兩種方法：事后統計法和事前估算法。事后統計法是將算法實現后計算其時間和空間開銷，從而確定算法的效率。然而，時間和空間開銷的計算與計算機軟硬件環境相關，同一個算法在不同的機器上執行所花的時間也不一樣，這種方法存在明顯的缺陷，因此，不予采納。本書采用事前估算法評估算法效率。

拋開與計算機軟硬件相關的因素，影響算法時間效率最主要的因素是問題規模。問題規模通常是指算法的輸入量，一般用整數n表示。例如，采用相同的排序算法對10個元素進行排序與對100 000個元素進行排序所需的時間顯然是不同的。

一個算法時間花銷與算法中語句的執行次數成正比例。算法中語句執行次數多，它的時間花銷就多。一個算法中的語句執行次數稱為語句頻度。

一般情況下，算法中基本運算執行次數用T(n)表示，若有問題規模n的某個函數f(n)，使存在自然數n0，正常數c，當n大于等于n0時，T(n)≤cf(n)，則稱f(n)是T(n)的漸近上界。記為

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

大O記號表示算法的一種漸近時間復雜度。漸近時間復雜度也常簡稱為時間復雜度。大O記號用以表達一個算法運行時間的上界，估計算法的執行時間的數量級。

下面舉例說明算法的漸近時間復雜度的求解。

程序1.1　簡單求和程序

程序1.1語句執行次數為5，算法的漸近時間復雜度為O(1)，屬于常數級。

程序1.2　累加求和程序

程序1.2語句執行次數為2n+4，算法的漸近時間復雜度T(n)=O(n)。

程序1.3　矩陣求和程序

程序1.3語句執行次數為3+n+1+n(n+1)+n2=2n2+2n+4，算法的漸近時間復雜度T(n)=O(n2)。

一般情況下，可以通過考察一個程序中的關鍵操作的執行次數來計算算法的漸近時間復雜度。所謂關鍵操作是對算法執行時間貢獻最大的操作。例如，程序1.2中，語句sum=sum+1可被認為是關鍵操作，其執行次數為n，由此計算可得算法的漸近時間復雜度也是O(n)。

常見的漸近時間復雜度從小到大依次是O(1)<O(log2 n)<O(n)<O(nlog2 n)<O(n2)<O(n3)。

1.4.3　最壞、最好和平均情況時間復雜度

算法的時間復雜度不僅與問題規模相關，如果輸入數據不同，算法所需的時間開銷也會不同。例如，在包含n個元素的數組中找給定元素x，設算法從左向右搜索，如果待搜索的元素x正好是第一個元素，則所需的查找時間最短，這就是算法的最好情況。如果待搜索的元素x是最后一個元素或是不在數組中，則是算法的最壞情況。如果需要多次在數組中查找元素，并且假定以相等的概率查找每個數組元素，則是算法時間代價的平均情況。

對于算法的時間復雜度分析，存在三種情況，對應三種時間復雜度，即最好情況、最壞情況和平均情況時間復雜度。相關示例將在后續章節中給出。

1.4.4　算法的空間復雜度

算法的空間復雜度往往是指對應的程序從運行開始到結束所需的存儲量。

程序運行所需的存儲空間包括兩部分。

（1）固定部分。這部分空間與問題規模無關，主要包括程序代碼、常量、簡單變量等所占的空間。

（2）可變部分。這部分空間大小與問題規模有關。例如，長度為1 000的兩個數組相加，與長度為10的兩個數組相加，所需的存儲空間是不同的。這部分存儲空間除了包括數據元素所占的空間外，還包括算法執行所需的額外空間，如遞歸棧所用的空間。

算法的空間復雜度的討論類似于時間復雜度，但空間復雜度一般按最壞情況來分析。