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

1.?兩種算法的比較

大家都已經學過一門計算機語言，不管學的是哪一種，學得好不好，好歹是可以寫點小程序了?，F(xiàn)在我要求你寫一個求1+2+3+……+100結果的程序，你應該怎么寫呢？

大多數(shù)人會馬上寫出下面的C語言代碼（或者其他語言的代碼）：

這是最簡單的計算機程序之一，它就是一種算法，我不去解釋這代碼的含義了。問題在于，你的第一直覺是這樣寫的，但這樣是不是真的很好？是不是最高效？

此時，我不得不把偉大數(shù)學家高斯的童年故事拿來說一遍，也許你們都早已經聽過，但不妨再感受一下，天才當年是如何展現(xiàn)天分和才華的。

據(jù)說18世紀生于德國小村莊的高斯，上小學的一天，課堂很亂，就像我們現(xiàn)在下面那些竊竊私語或者拿著手機不停擺弄的同學一樣，老師非常生氣，后果自然也很嚴重。于是老師在放學時，就要求每個學生都計算1+2+…+100的結果，誰先算出來誰先回家。天才當然不會被這樣的問題難倒，高斯很快就得出了答案，是5050。

老師非常驚訝，因為他自己想必也是通過1+2=3，3+3=6，6+4=10，……，4950+100=5050這樣算出來的，也算了很久很久。說不定為了怕錯，還算了兩三遍?？裳矍斑@個少年，為何可以這么快地得出結果？?

高斯解釋道：

用程序來實現(xiàn)如下：

?

神童就是神童，他用的方法相當于另一種求等差數(shù)列的算法，不僅僅可以用于1加到100，就是加到一千、一萬、一億（需要更改整型變量類型為長整型，否則會溢出），也就是瞬間之事。但如果用剛才的程序，顯然計算機要循環(huán)一千、一萬、一億次的加法運算。人腦比電腦算得快，似乎成為了現(xiàn)實。?

2.?算法定義

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

剛才的例子我們也看到，對于給定的問題，是可以有多種算法來解決的。算法定義中，提到了指令，指令能被人或機器等計算裝置執(zhí)行。它可以是計算機指令，也可以是我們平時的語言文字。為了解決某個或某類問題，需要把指令表示成一定的操作序列，操作序列包括一組操作，每一個操作都完成特定的功能，這就是算法了。

3. 算法的特性

算法具有五個基本特性：輸入、輸出、有窮性、確定性和可行性。

3.1?輸入輸出

輸入和輸出特性比較容易理解，算法具有零個或多個輸入。盡管對于絕大多數(shù)算法來說，輸入參數(shù)都是必要的，但對于個別情況，如打印“hello world！”這樣的代碼，不需要任何輸入參數(shù)，因此算法的輸入可以是零個。算法至少有一個或多個輸出，算法是一定需要輸出的，不需要輸出，你用這個算法干嗎？輸出的形式可以是打印輸出，也可以是返回一個或多個值等。

3.2?有窮性

有窮性：指算法在執(zhí)行有限的步驟之后，自動結束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內完成。現(xiàn)實中經常會寫出死循環(huán)的代碼，這就是不滿足有窮性。當然這里有窮的概念并不是純數(shù)學意義的，而是在實際應用當中合理的、可以接受的“有邊界”。你說你寫一個算法，計算機需要算上個二十年，一定會結束，它在數(shù)學意義上是有窮了，可是媳婦都熬成婆了，算法的意義也不就大了。

3.3?確定性

確定性：算法的每一步驟都具有確定的含義，不會出現(xiàn)二義性。?算法在一定條件下，只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結果。算法的每個步驟被精確定義而無歧義。

3.4?可行性

可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。可行性意味著算法可以轉換為程序上機運行，并得到正確的結果。盡管在目前計算機界也存在那種沒有實現(xiàn)的極為復雜的算法，不是說理論上不能實現(xiàn)，而是因為過于復雜，我們當前的編程方法、工具和大腦限制了這個工作，不過這都是理論研究領域的問題，不屬于我們現(xiàn)在要考慮的范圍。

4. 算法設計的要求

4.1正確性

算法的“正確”通常分為以下四個層次。

1．算法程序沒有語法錯誤。

2．算法程序對于合法的輸入數(shù)據(jù)能夠產生滿足要求的輸出結果。

3．算法程序對于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結果。

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

對于這四層含義，層次1要求最低，但是僅僅沒有語法錯誤實在談不上是好算法。這就如同僅僅解決溫飽，不能算是生活幸福一樣。而層次4是最困難的，我們幾乎不可能逐一驗證所有的輸入都得到正確的結果。因此算法的正確性在大部分情況下都不可能用程序來證明，而是用數(shù)學方法證明的。證明一個復雜算法在所有層次上都是正確的，代價非常昂貴。所以一般情況下，我們把層次3作為一個算法是否正確的標準。

4.2?可讀性

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

可讀性高有助于人們理解算法，晦澀難懂的算法往往隱含錯誤，不易被發(fā)現(xiàn)，并且難于調試和修改。

我們寫代碼的目的，一方面是為了讓計算機執(zhí)行，但還有一個重要的目的是為了便于他人閱讀，讓人理解和交流，自己將來也可能閱讀，如果可讀性不好，時間長了自己都不知道寫了些什么?？勺x性是算法（也包括實現(xiàn)它的代碼）好壞很重要的標志。

4.3?健壯性

一個好的算法還應該能對輸入數(shù)據(jù)不合法的情況做合適的處理。比如輸入的時間或者距離不應該是負數(shù)等。

健壯性：當輸入數(shù)據(jù)不合法時，算法也能做出相關處理，而不是產生異?；蚰涿畹慕Y果。

4.4?時間效率高和存儲量低

時間效率指的是算法的執(zhí)行時間，對于同一個問題，如果有多個算法能夠解決，執(zhí)行時間短的算法效率高，執(zhí)行時間長的效率低。

存儲量需求指的是算法在執(zhí)行過程中需要的最大存儲空間，主要指算法程序運行時所占用的內存或外部硬盤存儲空間。

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

5. 算法效率的度量方法

5.1?事后統(tǒng)計方法

事后統(tǒng)計方法：這種方法主要是通過設計好的測試程序和數(shù)據(jù)，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低。

但這種方法顯然是有很大缺陷的：

■ 必須依據(jù)算法事先編制好程序，這通常需要花費大量的時間和精力。如果編制出來發(fā)現(xiàn)它根本是很糟糕的算法，不是竹籃打水一場空嗎？

■ 時間的比較依賴計算機硬件和軟件等環(huán)境因素，有時會掩蓋算法本身的優(yōu)劣。要知道，現(xiàn)在的一臺四核處理器的計算機，跟當年286、386、486等老爺爺輩的機器相比，在處理算法的運算速度上，是不能相提并論的；而所用的操作系統(tǒng)、編譯器、運行框架等軟件的不同，也可以影響它們的結果；就算是同一臺機器，CPU使用率和內存占用情況不一樣，也會造成細微的差異。

■ 算法的測試數(shù)據(jù)設計困難，并且程序的運行時間往往還與測試數(shù)據(jù)的規(guī)模有很大關系，效率高的算法在小的測試數(shù)據(jù)面前往往得不到體現(xiàn)。比如10個數(shù)字的排序，不管用什么算法，差異幾乎是零。而如果有一百萬個隨機數(shù)字排序，那不同算法的差異就非常大了。那么我們?yōu)榱吮容^算法，到底用多少數(shù)據(jù)來測試，這是很難判斷的問題。

基于事后統(tǒng)計方法有這樣那樣的缺陷，我們考慮不予采納。

5.2?事前分析估算方法

我們的計算機前輩們，為了對算法的評判更科學，研究出了一種叫做事前分析估算的方法。

事前分析估算方法：在計算機程序編制前，依據(jù)統(tǒng)計方法對算法進行估算。

經過分析，我們發(fā)現(xiàn)，一個用高級程序語言編寫的程序在計算機上運行時所消耗的時間取決于下列因素：

1．算法采用的策略、方法。

2．編譯產生的代碼質量。

3．問題的輸入規(guī)模。

4．機器執(zhí)行指令的速度。

第1條當然是算法好壞的根本，第2條要由軟件來支持，第4條要看硬件性能。也就是說，拋開這些與計算機硬件、軟件有關的因素，一個程序的運行時間，依賴于算法的好壞和問題的輸入規(guī)模。所謂問題輸入規(guī)模是指輸入量的多少。

我們來看看今天剛上課時舉的例子，兩種求和的算法：

顯然，第一種算法，執(zhí)行了1+（n+1）+n+1次=2n+3次；而第二種算法，是1+1+1=3次。事實上兩個算法的第一條和最后一條語句是一樣的，所以我們關注的代碼其實是中間的那部分，我們把循環(huán)看作一個整體，忽略頭尾循環(huán)判斷的開銷，那么這兩個算法其實就是n次與1次的差距。算法好壞顯而易見。?

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

這個例子中，i從1到100，每次都要讓j循環(huán)100次，而當中的x++和sum=sum+x；其實就是1+2+3+…+10000，也就是100^2次，所以這個算法當中，循環(huán)部分的代碼整體需要執(zhí)行n^2（忽略循環(huán)體頭尾的開銷）次。

顯然這個算法的執(zhí)行次數(shù)對于同樣的輸入規(guī)模n=100，要多于前面兩種算法，這個算法的執(zhí)行時間隨著n的增加也將遠遠多于前面兩個。

此時你會看到，測定運行時間最可靠的方法就是計算對運行時間有消耗的基本操作的執(zhí)行次數(shù)。運行時間與這個計數(shù)成正比。

我們不關心編寫程序所用的程序設計語言是什么，也不關心這些程序將跑在什么樣的計算機中，我們只關心它所實現(xiàn)的算法。這樣，不計那些循環(huán)索引的遞增和循環(huán)終止條件、變量聲明、打印結果等操作，最終，在分析程序的運行時間時，最重要的是把程序看成是獨立于程序設計語言的算法或一系列步驟。

可以從問題描述中得到啟示，同樣問題的輸入規(guī)模是n，求和算法的第一種，求1+2+…+n需要一段代碼運行n次。那么這個問題的輸入規(guī)模使得操作數(shù)量是f（n）=n，顯然運行100次的同一段代碼規(guī)模是運算10次的10倍。而第二種，無論n為多少，運行次數(shù)都為1，即f（n）=1；第三種，運算100次是運算10次的100倍。因為它是f（n）=n2。

我們在分析一個算法的運行時間時，重要的是把基本操作的數(shù)量與輸入規(guī)模關聯(lián)起來，即基本操作的數(shù)量必須表示成輸入規(guī)模的函數(shù)。

我們可以這樣認為，隨著n值的越來越大，它們在時間效率上的差異也就越來越大。好比你們當中有些人每天都在學習，我指有用的學習，而不是只為考試的死讀書，每天都在進步，而另一些人，打打游戲，睡睡大覺。入校時大家都一樣，但畢業(yè)時結果可能就大不一樣，前者名企爭搶著要，后者求職無門。

5.3?函數(shù)的漸近增長

我們現(xiàn)在來判斷一下，兩個算法A和B哪個更好。假設兩個算法的輸入規(guī)模都是n，算法A要做2n+3次操作，你可以理解為先有一個n次的循環(huán)，執(zhí)行完成后，再有一個n次循環(huán)，最后有三次賦值或運算，共2n+3次操作。算法B要做3n+1次操作。你覺得它們誰更快呢？

準確說來，答案是不一定的

當n=1時，算法A效率不如算法B（次數(shù)比算法B要多一次）。而當n=2時，兩者效率相同；當n > 2時，算法A就開始優(yōu)于算法B了，隨著n的增加，算法A比算法B越來越好了（執(zhí)行的次數(shù)比B要少）。于是我們可以得出結論，算法A總體上要好過算法B。

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

函數(shù)的漸近增長：給定兩個函數(shù)f（n）和g（n），如果存在一個整數(shù)N，使得對于所有的n > N，f（n）總是比g（n）大，那么，我們說f（n）的增長漸近快于g（n）。

從中我們發(fā)現(xiàn)，隨著n的增大，后面的+3還是+1其實是不影響最終的算法變化的，例如算法A′與算法B′，所以，我們可以忽略這些加法常數(shù)。后面的例子，這樣的常數(shù)被忽略的意義可能會更加明顯。

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

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

判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常?？梢院雎裕鼞撽P注主項（最高階項）的系數(shù)。判斷一個算法好不好，我們只通過少量的數(shù)據(jù)是不能做出準確判斷的。根據(jù)剛才的幾個樣例，我們發(fā)現(xiàn)，如果我們可以對比這幾個算法的關鍵執(zhí)行次數(shù)函數(shù)的漸近增長性，基本就可以分析出：某個算法，隨著n的增大，它會越來越優(yōu)于另一算法，或者越來越差于另一算法。這其實就是事前估算方法的理論依據(jù)，通過算法時間復雜度來估算算法時間效率。

5.4?算法時間復雜度

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

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

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

顯然，由此算法時間復雜度的定義可知，我們的三個求和算法的時間復雜度分別為O(n)，O(1)，O(n2)。我們分別給它們取了非官方的名稱，O(1)叫常數(shù)階、O(n)叫線性階、O(n2)叫平方階，當然，還有其他的一些階，我們之后會介紹。

5.5 推導大O階方法

那么如何分析一個算法的時間復雜度呢？即如何推導大O階呢？我們給出了下面的推導方法，基本上，這也就是總結前面我們舉的例子。

推導大O階：

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

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

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

哈，仿佛是得到了游戲攻略一樣，我們好像已經得到了一個推導算法時間復雜度的萬能公式?？墒聦嵣?，分析一個算法的時間復雜度，沒有這么簡單，我們還需要多看幾個例子。

a 常數(shù)階

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

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

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

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

注意：不管這個常數(shù)是多少，我們都記作O(1)，而不能是O(3)、O(12)等其他任何數(shù)字，這是初學者常常犯的錯誤。?

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

b?線性階

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

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

c?對數(shù)階

下面的這段代碼，時間復雜度又是多少呢？

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

d?平方階

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

而對于外層的循環(huán)，不過是內部這個時間復雜度為O(n)的語句，再循環(huán)n次。所以這段代碼的時間復雜度為O(n2)。如果外循環(huán)的循環(huán)次數(shù)改為了m，時間復雜度就變?yōu)镺(m×n)。

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

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

由于當i=0時，內循環(huán)執(zhí)行了n次，當i=1時，執(zhí)行了n－1次，……當i=n－1時，執(zhí)行了1次。所以總的執(zhí)行次數(shù)為：

?

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

從這個例子，我們也可以得到一個經驗，其實理解大O推導不算難，難的是對數(shù)列的一些相關運算，這更多的是考察你的數(shù)學知識和能力。

e 方法調用的時間復雜度

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

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

假如function是下面這樣的：

事實上，這和剛才舉的例子是一樣的，只不過把嵌套內循環(huán)放到了函數(shù)中，所以最終的時間復雜度為O(n^2)。

下面這段相對復雜的語句：

它的執(zhí)行次數(shù)

根據(jù)推導大O階的方法，最終這段代碼的時間復雜度也是O(n2)。?

6.?常見的時間復雜度

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

我們前面已經談到了O(1)常數(shù)階、O(logn)對數(shù)階、O(n)線性階、O(n2)平方階等，至于O(nlogn)我們將會在今后的課程中介紹，而像O(n3)，過大的n都會使得結果變得不現(xiàn)實。同樣指數(shù)階O(2n)和階乘階O(n!)等除非是很小的n值，否則哪怕n只是100，都是噩夢般的運行時間。所以這種不切實際的算法時間復雜度，一般我們都不去討論它。

7.?最壞情況與平均情況

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

算法的分析也是類似，我們查找一個有n個隨機數(shù)字數(shù)組中的某個數(shù)字，最好的情況是第一個數(shù)字就是，那么算法的時間復雜度為O(1)，但也有可能這個數(shù)字就在最后一個位置上待著，那么算法的時間復雜度就是O(n)，這是最壞的一種情況了。最壞情況運行時間是一種保證，那就是運行時間將不會再壞了。在應用中，這是一種最重要的需求，通常，除非特別指定，我們提到的運行時間都是最壞情況的運行時間。

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

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

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

8.?算法空間復雜度

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

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

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

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

通常，我們都使用“時間復雜度”來指運行時間的需求，使用“空間復雜度”指空間需求。當不用限定詞地使用“復雜度”時，通常都是指時間復雜度。顯然我們這本書重點要講的還是算法的時間復雜度的問題。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-853998.html

到了這里，關于《大話數(shù)據(jù)結構》02 算法的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！