數據結構溢彩加強版——（二）算法篇

算法：算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，并且每條指令表示一個或多個操作。

@[toc]

兩種算法的比較

要求寫一個求1+2+3+……+100結果的程序

int i , sum = 0, n = 100; for(int = 1; i <= n; i++) { sum = sum + i; } printf("%d ", sum);

用程序來實現如下：

int sum = 0, n = 100; sum = (1 + n) * n / 2; printf("%d "sum);

算法的特征

1.輸入輸出

算法具有零個或多個輸入；算法至少一個或多個輸出。

2.有窮性

有窮性：指算法在執行有限的步驟之后，自動結束而不會出現無限循環，并且每一個步驟在可接受的時間內完成。

3.確定性

確定性：算法的每一步驟都具有有確定的含義，不會出現二義性。

4.可行性

可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限次數完成。

算法設計的要求

1.正確性

正確性：算法的正確性是指算法至少應該具有輸入，輸出和加工處理無歧義性，能正確反映問題的需求，能夠得到問題的正確答案。

但是算法的“正確”通常在用法上有很大的差別，大體分為一下四個層次：

（1）算法程序沒有語法錯誤。

（2）算法程序對于合法的輸入數據能夠產生滿足要求的輸出結果。

（3）算法程序對于非法的輸入數據能夠得出滿足規格說明的結果

（4）算法程序對于精心選擇的，甚至刁難的測試數據都有滿足要求的輸出結果。

2.可讀性

可讀性：算法程序設計的另一目的是為了便于閱讀，理解和交流。

3.健壯性

健壯性：當輸入數據不合法時，算法也能做出相應的處理，而不是產生異常或莫名奇妙的結果。

4.時間效率高和存儲量低

設計算法應該盡量滿足時間效率高和存儲量低的需求。

算法效率的度量方法

1.事后統計方法

1.事后統計法

衡量算法效率最簡單的一個辦法就是把算法變成一個程序，然后再機器上執行，然后計時，這就是事后統計法。

這樣顯然有一些缺點：

（1）必須到機器上去計算，而且這個計算不只是一次，我們要用多組數據對其進行重復的運算，然后得到一個統計的結果，那么你要算上機器的時間。

（2）肯定會有一些其他因素掩蓋算法的本質。

2.事前分析估算法

通常比較算法好壞，都是在設計算法的時候就應該知道它的效率，這就是事前分析估算法。

說明： 要比較兩個算法，實際上在設計的時候就做著工作來衡量它們的效率，因此更常用的方法是事前分析估算法。

我們來看看兩種求和的算法：

第一種算法：

int i, sum = 0, n = 100; /*執行一次*/ for(i = 1; i<= n; i++) /*執行了n+1次*/ { sum = sum + i; /*執行n次*/ } printf("%d ",sum); /*執行一次*/

第二種算法：

int sum = 0, n = 100; /*執行一次*/ sum = (1 + n) * n / 2; /*執行一次*/ printf("%d "sum); /*執行一次*/

顯然，第一種算法，執行了1+(n+1)+n+1次=2n+3次；而第二種算法，是1+1+1=3次。

我們再來延伸一下上面這個例子：

int x, j, x = 0, sum = 0, n = 100; /*執行1次*/ for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { x++; /*執行n*n次*/ sum = sum + x; } } printf("%d ",sum); /*執行1次*/

在這個例子中，i到1到100，每次都要讓j循環100次，而當中x++和sum=sum+x;其實就是1+2+3+……+10000，也就是1002次，所以這個算法當中，循環部分的代碼整體需要執行n2。

此時你會看到，測試運行時間最可靠的方法就是計算對運行時間有消耗的基本操作的執行次數，運行時間與這個數成正比。最終，在分析程序的運行期間時，最終要的是把程序看成是獨立于程序設計語言的算法或一系列步驟。

函數的漸近增長

我們先通過一個例子來看一下，假設兩個算法的輸入規模都是n，算法A要做2n+3次操作，可以理解為先有一個n次的循環，執行完成后，再有一個n次的循環，最后有三次賦值或運算，共2n+3次操作，算法B要做3n+!次操作，那么這兩個算法那個更快呢？

當n = 1時，算法A的效率不如算法B(次數比B多一次)。而當n = 2時，兩者效率相同；當n >2時，算法A就開始優于算法B了，隨著n的增加，算法A比算法B越來越好了。我們可以說，算法A總體上要好于算法B。

此時我們給出這樣的定義，輸入規模n在沒有限制的情況下，只要超過一個數值N，這個函數就總是大于另一個函數，我們稱函數是漸進增長的。

函數的漸進增長：給定兩個函數 f (n) 和 g (n)，如果存在一個整數N，使得對于所有的 n > N，f (n)總是比 g (n) 大，那么，就可以說 f (n) 的漸進增長大于 g (n) 。

從中我們可以發現，隨著n的增大，后面的+3還是+1其實是不影響最終的算法變化的，所以，我們可以忽略這些加法常數。

再來看第二個例子，算法C是4n + 8，算法D是2n2 + 1。

當n≤3的時候，算法C要差于算法D（因為算法C次數比較多），但當n>3后，算法C的優勢就越來越優于算法D了，到后來更是遠遠勝過。而當后面的常數去掉后，我們發現其實結果沒有發生改變。甚至我們再觀察發現，哪怕去掉與n相乘的常數，這樣的結果也沒發生改變，算法C′的次數隨著n的增長，還是遠小于算法D′。也就是說，與最高次項相乘的常數并不重要。

再看第三個例子，算法E是2n2+3n+1，算法F是2n3+3n+1。

請添加圖片描述

當n=1的時候，算法E與算法F結果相同，但當n>1后，算法E的優勢就要開始優于算法F，隨著n的增大，差異非常明顯。通過觀察發現，最高次項的指數大的，函數隨著n的增長，結果也會變得增長特別快。

來看最后一個例子。算法G是2n2，算法H是3n+1，算法I是2n2+3n+1。

這組數據應該就看得很清楚。當n的值越來越大時，你會發現，3n+1已經沒法和2n2的結果相比較，最終幾乎可以忽略不計。也就是說，隨著n值變得非常大以后，算法G其實已經很趨近于算法I。于是我們可以得到這樣一個結論，判斷一個算法的效率時，函數中的常數和其他次要項常常可以忽略，而更應該關注主項（最高階項）的階數。

判斷一個算法好不好，我們只通過少量的數據是不能做出準確判斷的。根據剛才的幾個樣例，我們發現，如果我們可以對比這幾個算法的關鍵執行次數函數的漸近增長性，基本就可以分析出：某個算法，隨著n的增大，它會越來越優于另一算法，或者越來越差于另一算法。這其實就是事前估算方法的理論依據，通過算法時間復雜度來估算算法時間效率。

算法時間復雜度

1.算法時間復雜度定義

在進行算法分析時，語句總的執行次數T (n)是關于問題規模n的函數，進而分析 T (n) 隨 n 的變化情況并確定 T (n) 的數量級。算法的時間復雜度，也就是算法的時間量度，記作：T (n) = O (f(n))。它表示隨問題規模 n 的增大，算法執行時間的增長率和 f (n) 的增長率相同，稱作算法的漸近時間復雜度，簡稱為時間復雜度。其中 f (n)是問題規模 n 的某個函數。

這樣用大寫O( )來體現算法時間復雜度的記法，我們稱之為大O記法。

一般情況下，隨著n的增大，T(n)增長最慢的算法為最優算法。

顯然，由此算法時間復雜度的定義可知，在函數的漸進增長一文中前三個例子的求和算法的時間復雜度分別為O(n)，O(1)，O(n2)。我們分別可以稱之為，O(1)叫常數階、O(n)叫線性階、O(n2)叫平方階，當然，還有其他的一些階，請接著往下看！

2.推導大o階方法

(1)．用常數1取代運行時間中的所有加法常數。

(2)．在修改后的運行次數函數中，只保留最高階項。

(3)．如果最高階項存在且不是1，則去除與這個項相乘的系數，得到的結果就是大O階。

3.常數階

首先順序結構的時間復雜度。下面這個算法，也就是高斯算法，為什么時間復雜度不是O(3)，而是O(1)。

int sum = 0, n = 100; /* 執行一次 */ sum = (1 + n) * n / 2; /* 執行一次 */ printf("%d",sum); /* 執行一次 */

這個算法的運行次數函數是f(n)=3。根據我們推導大O階的方法，第一步就是把常數項3改為1。在保留最高階項時發現，它根本沒有最高階項，所以這個算法的時間復雜度為O(1)。

另外，我們試想一下，如果這個算法當中的語句sum=(1+n)*n/2有10句，即：

int sum = 0, n = 100; /*執行1次*/ sum = (1+n) *n/2; /*執行第1次*/ sum = (1+n) *n/2; /*執行第2次*/ sum = (1+n) *n/2; /*執行第3次*/ sum = (1+n) *n/2; /*執行第4次*/ sum = (1+n) *n/2; /*執行第5次*/ sum = (1+n) *n/2; /*執行第6次*/ sum = (1+n) *n/2; /*執行第7次*/ sum = (1+n) *n/2; /*執行第8次*/ sum = (1+n) *n/2; /*執行第9次*/ sum = (1+n) *n/2; /*執行第10次*/ printf("%d ",sum); /*執行1次*/

事實上無論n為多少，上面的兩段代碼就是3次和12次執行的差異。這種與問題的大小無關（n的多少），執行時間恒定的算法，我們稱之為具有O(1)的時間復雜度，又叫常數階。

注意：不管這個常數是多少，我們都記作 O（1），而不能是O（3），O（12）等其它任何數學，這就是初學者嘗嘗犯的錯誤。

對于分支結構而言，無論是真，還是假，執行的次數都是恒定的，不會隨著n的變大而發生變化，所以單純的分支結構（不包含在循環結構中），其時間復雜度也是O(1)。

4.線性階

線性階的循環結構會復雜很多。要確定某個算法的階次，我們常常需要確定某個特定語句或某個語句集運行的次數。因此，我們要分析算法的復雜度，關鍵就是要分析循環結構的運行情況。

下面這段代碼，它的循環的時間復雜度為O(n)，因為循環體中的代碼須要執行n次。

int i; for (i = 0; i < n; i++) { /* 時間復雜度為O(1)的程序步驟序列 */ }

5.對數階

來看一下下面這段代碼的時間復雜度是多少？

int count = 1; while (count < n) { count = count * 2; /* 時間復雜度為O(1)的程序步驟序列 */ }

由于每次count乘以2之后，就距離n更近了一分。也就是說，有多少個2相乘后大于n，則會退出循環。由2x(次冪)=n得到x=log2n。所以這個循環的時間復雜度為O(logn)。

6.平方階

下面例子是一個循環嵌套，它的內循環剛才我們已經分析過，時間復雜度為O(n)。

int i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { /* 時間復雜度為O(1)的程序步驟序列 */ } }

而對于外層的循環，不過是內部這個時間復雜度為O(n)的語句，再循環n次。所以這段代碼的時間復雜度為O(n2)(n的平方)。

如果外循環的循環次數改為了m，時間復雜度就變為O(m×n)。

int i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { /* 時間復雜度為O(1)的程序步驟序列 */ } }

所以我們可以總結得出，循環的時間復雜度等于循環體的復雜度乘以該循環運行的次數。

那么下面這個循環嵌套，它的時間復雜度是多少呢？

int i, j; for (i = 0; i < n; i++) { /* 注意j = i 而不是0 */ for (j = i; j < n; j++) { /* 時間復雜度為O(1)的程序步驟序列 */ } }

由于當i=0時，內循環執行了n次，當i=1時，執行了n-1次，……當i=n-1時，執行了1次。所以總的執行次數為：

n + (n - 1) + (n - 2) + … + 1 = n(n+1) / 2 = n^2 / 2 + n / 2

用推導大O階的方法，第一條，沒有加法常數不予考慮；第二條，只保留最高階項，因此保留n2/2；第三條，去除這個項相乘的常數，也就是去除1/2，最終這段代碼的時間復雜度為O(n2)。

接下來看一下對于方法調用的時間復雜度該怎樣分析。

int i, j; for (i = 0; i

上面這段代碼調用一個函數 function()。

void function(int count) { print(count); }

函數體是打印這個參數。其實這很好理解，function函數的時間復雜度是O(1)。所以整體的時間復雜度為O(n)。

如果 function 是下面這樣的：

void function(int count) { int j; for (j = count; j < n; j++) { /* 時間復雜度為O(1)的程序步驟序列 */ } }

事實上，這和上面舉的例子是一樣的，只不過把嵌套內循環放到了函數中，所以最終的時間復雜度為O(n2)。

常見的時間復雜度

最后我們來看一下常見的時間復雜度有哪些吧：

執行次數 函數階 非正式術語

常用的時間復雜度所耗費的時間從小到大依次是：

O(1)

最壞情況與平均情況

你早晨上班出門后突然想起來，手機忘記帶了，這年頭，鑰匙、錢包、手機三大件，出門哪樣也不能少呀。于是回家找。打開門一看，手機就在門口玄關的臺子上，原來是出門穿鞋時忘記拿了。這當然是比較好，基本沒花什么時間尋找。可如果不是放在那里，你就得進去到處找，找完客廳找臥室、找完臥室找廚房、找完廚房找衛生間，就是找不到，時間一分一秒的過去，你突然想起來，可以用家里座機打一下手機，聽著手機鈴聲來找呀，真是笨。終于找到了，在床上枕頭下面。你再去上班，遲到。見鬼，這一年的全勤獎，就因為找手機給黃了。

找東西有運氣好的時候，也有怎么也找不到的情況。但在現實中，通常我們碰到的絕大多數既不是最好的也不是最壞的，所以算下來是平均情況居多。

算法的分析也是類似，我們查找一個有n個隨機數字數組中的某個數字，最好的情況是第一個數字就是，那么算法的時間復雜度為O(1)，但也有可能這個數字就在最后一個位置上待著，那么算法的時間復雜度就是O(n)，這是最壞的一種情況了。

最壞情況運行時間是一種保證，那就是運行時間將不會再壞了。在應用中，這是一種最重要的需求，通常，除非特別指定，我們提到的運行時間都是最壞情況的運行時間。

而平均運行時間也就是從概率的角度看，這個數字在每一個位置的可能性是相同的，所以平均的查找時間為n/2次后發現這個目標元素。

平均運行時間是所有情況中最有意義的，因為它是期望的運行時間。也就是說，我們運行一段程序代碼時，是希望看到平均運行時間的。可現實中，平均運行時間很難通過分析得到，一般都是通過運行一定數量的實驗數據后估算出來的。

對算法的分析，一種方法是計算所有情況的平均值，這種時間復雜度的計算方法稱為平均時間復雜度。另一種方法是計算最壞情況下的時間復雜度，這種方法稱為最壞時間復雜度。一般在沒有特殊說明的情況下，都是指最壞時間復雜度。

算法空間復雜度

我們在寫代碼時，完全可以用空間來換取時間，比如說，要判斷某某年是不是閏年，你可能會花一點心思寫了一個算法，而且由于是一個算法，也就意味著，每次給一個年份，都是要通過計算得到是否是閏年的結果。還有另一個辦法就是，事先建立一個有2050個元素的數組（年數略比現實多一點），然后把所有的年份按下標的數字對應，如果是閏年，此數組項的值就是1，如果不是值為0。這樣，所謂的判斷某一年是否是閏年，就變成了查找這個數組的某一項的值是多少的問題。此時，我們的運算是最小化了，但是硬盤上或者內存中需要存儲這2050個0和1。

這是通過一筆空間上的開銷來換取計算時間的小技巧。到底哪一個好，其實要看你用在什么地方。

算法的空間復雜度通過計算算法所需的存儲空間實現，算法空間復雜度的計算公式記作：S(n)=O(f(n))，其中，n為問題的規模，f(n)為語句關于n所占存儲空間的函數。

一般情況下，一個程序在機器上執行時，除了需要存儲程序本身的指令、常數、變量和輸入數據外，還需要存儲對數據操作的存儲單元。若輸入數據所占空間只取決于問題本身，和算法無關，這樣只需要分析該算法在實現時所需的輔助單元即可。若算法執行時所需的輔助空間相對于輸入數據量而言是個常數，則稱此算法為原地工作，空間復雜度為O(1)。

通常，我們都使用“時間復雜度”來指運行時間的需求，使用“空間復雜度”指空間需求。當不用限定詞地使用“復雜度”時，通常都是指時間復雜度。

總結與回顧

。。。。。。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。