1.3.3　算法分析

在計算機解決問題的過程中，數據結構和算法是程序的兩大要素，二者相輔相成，缺一不可。算法與數據結構的好壞直接相關，一種數據結構的優劣是由實現其各種運算的算法體現的。對數據結構的分析實質上也表現為對實現其多種運算的算法分析。算法分析是一個復雜的問題，它首先涉及優劣準則的確定。判斷一個算法的優劣主要有以下幾個標準：

（1）正確性。要求算法能夠正確地執行規定的功能。這是最重要也是最基本的準則。

（2）可使用性。算法應當是可讀的，即可讀性好。為了達到這個要求，算法的邏輯必須是清晰的、簡單的和結構化的。

（3）健壯性。要求算法具有很好的容錯性，即提供例外處理，能夠對不合理的數據和操作進行檢查，不會經常出現異常中斷或死機現象。

（4）效率。算法的效率主要指算法執行時計算機資源的消耗，包括存儲和運行時間的開銷，前者叫做算法的空間代價，后者叫做算法的時間代價。

時間代價是常用的評價指標，往往用時間復雜度來衡量。當一個算法轉換成程序并在計算機上執行時，其運行所需要的時間總是取決于下列因素：

①硬件的速度。CPU速度和存取數據的速度越快，則程序的執行時間越短。

②所選用的程序設計語言。程序設計語言的級別越高，其執行效率就越低。例如，匯編語言程序的執行效率往往要高于高級算法語言。

③編譯程序所生成目標代碼的質量。對于代碼優化較好的編譯程序，其所生成的程序質量較高。例如，代碼效率優化過的C++語言程序比未經過優化的代碼效率要高。

④問題的規模。很顯然，大規模的問題求解過程比小規模的問題更耗費時間。

顯然，在各種因素都不能確定的情況下，很難比較算法的執行時間。也就是說，使用執行算法的絕對時間來衡量算法的效率是不合適的。為此，可以將上述各種與計算機相關的軟、硬件因素都確定下來，這樣一個特定算法的運行工作量的大小就只依賴于問題的規模，或者說它是問題規模的函數。另一方面，要全面地評價一個算法的優劣，不僅要考慮時間的耗費，還要考慮算法對存儲器的耗費。特別是對于規模大的問題，對空間耗費的分析是必不可少的。因此，分別有基于時間和空間的算法分析，即算法的時間復雜度分析和空間復雜度分析。

1.時間復雜度

時間復雜度（Time Complexity）又稱計算復雜度，它是一個算法運行時間的相對度量。一個程序的時間復雜度是指程序從開始到結束運行所需要的時間。

任何一個算法都是由一個控制結構和若干原操作組成的。該算法的執行時間取決于兩者的綜合效果。所謂“原操作”，是指程序設計語言中允許的數據類型（稱為固有數據類型）的操作（如賦值、比較、計算、轉向、返回、輸入、輸出等），算法的執行時間大致等于計算機一次原操作所需時間與算法中進行簡單操作次數的乘積，即

算法的執行時間=原操作的執行次數之和×原操作的執行時間

因為原操作的執行時間相對問題規模而言是個常量，則算法的執行時間與原操作執行次數之和成正比。同時，由于估算算法時間復雜度關心的只是算法執行時間的增長率而非絕對時間，因此可以忽略一些次要因素。從算法中選取一種對于所研究的問題來說是基本操作的原操作，以其在算法中重復執行的次數作為算法時間復雜度的依據，這種衡量效率的辦法所得出的時間量是一種增長趨勢的量度，它與軟、硬件環境無關，只體現算法本身執行效率的優劣。

為了便于比較同一問題的不同算法，通常的做法是：從算法中選取一種對于所研究的問題來說是基本運算的原操作，以該原操作重復執行的次數作為算法的時間度量。一般情況下，算法中原操作重復執行的次數是規模n（通常用正整數n表示）的某個函數T（n），即要體現算法執行時間隨問題規模的增長而增長的趨勢。

許多時候要精確地計算T（n）是困難的，假如隨時間問題規模n的增長，算法執行時間的增長率和f（n）的增長率相同，我們引入漸進時間復雜度，在數量上估計一個算法的執行時間，也能夠達到分析算法的目的。

定義：如果存在兩個正常數c和n0，使得對所有的n，n≥n0，有f（n）≤c·g（n），則記為T（n）=O（g（n））。

使用記號O表示的算法的時間復雜度稱為算法的漸進時間復雜度（Asymptotic Complexity）。例如，一個程序的實際執行時間為T（n）=2.7n3+3.8n2+5.3，則T（n）=O（n3）。

通常用O（1）表示常數計算時間。常見的漸進時間復雜度有：

O（1）<O（log2n）<O（n）<O（nlog2n）<O（n2）<O（n3）<O（2n）

隨著問題規模的增大，算法的時間消耗也在增大，但不同算法的增長趨勢往往是不同的。如果對于一個問題所設計的兩種不同算法，算法A的時間復雜度為O（n2），算法B的時間復雜度為O（log2n），則隨著問題規模n的增大，算法A所消耗時間迅速增大，而算法B所消耗時間的增大趨向平緩。顯然，在問題的規模很大時，算法B運行效率高，可以認為算法B優于算法A。

2.空間復雜度

一個程序的空間復雜度（Space Complexity）是指程序運行從開始到結束所需的存儲量。算法的存儲量是指算法執行過程中所需的最大存儲空間。程序的一次運行是針對所求解的問題的某一特定實例而言的。例如，排序算法每次的執行過程是對一組特定個數的元素進行排序，對該組元素的排序是排序問題的一個實例，元素個數可視為該實例的特征。

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

（1）固定部分。這部分空間與所處理數據的大小和個數無關，或者稱與問題實例的特征無關。主要包括程序代碼、常量、簡單變量、定長成分的結構變量所占的空間。

（2）可變部分。這部分空間大小與算法在某次執行中處理的特定數據的大小和規模有關。例如，100個數據元素的排序算法與1000個數據元素的排序算法所需的存儲空間顯然是不同的。

若輸入數據所占空間只取決于問題本身，和算法無關，則在比較算法時可以不加考慮輸入的數據。一般來說，利用代碼本身所占空間對不同算法也不會有數量級的差別，因此只需要分析輸入的數據和程序代碼之外的額外空間。類似于算法的時間復雜度，通常以算法的空間復雜度作為算法所需存儲空間的量度。定義算法空間復雜度為

S（n）=O（g（n））

空間復雜度也是問題規模n的函數。表示隨問題規模n的增大，算法運行所需存儲量的增長率與g（n）的增長率相同。

和算法時間復雜度的考慮情況相似，若算法所需存儲量依賴于特定的輸入數據，則通常按最壞的情況考慮。

例如，求4×4矩陣元素的和。

則該問題的規模n=4，頻度為f（4）=4×4，時間復雜度為T（4）=O（f（4））。

應根據具體的情況來選取合適的算法。一般來說，對于反復使用的程序，應選取運行時間短的算法；而當涉及的數據量極大，機器的存儲空間較小時，應選用節約存儲空間的算法。需要說明的是，應該選用一個運行時間短、所占空間小、其他性能也好的算法。然而，實際上很難找到這樣完美的算法，因為若想節約算法的執行時間，往往要以犧牲存儲空間為代價，而為了節省存儲空間，就要以耗費更多的計算時間來補償。