跟隨本教程學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，我們會給大家講解一些與數(shù)據(jù)結(jié)構(gòu)聯(lián)系緊密的算法。

所謂算法，簡單理解就是解決問題的方法（方案、思路）。通常情況下，一個問題的解決方法會有很多種，或者說解決這個問題的算法有很多種。

舉個簡單的例子，對數(shù)據(jù)集{2,4,5,1,3}做升序排序，解決這個問題的算法就有很多種，比如冒泡排序算法、快速排序算法、歸并排序算法、希爾排序算法等。借助任何一種算法，都可以得到{1,2,3,4,5}升序序列。

同一個問題，使用不同的算法，雖然都可以解決問題，但有的算法執(zhí)行效率高，有的算法執(zhí)行效率低。就好比擰一個螺母，使用鉗子和扳手都可以，但顯然扳手?jǐn)Q螺母的效率更高。那么問題就出現(xiàn)了，怎樣從眾多算法中選擇出“最好”的呢？

算法本身是不分“好壞”的，所謂“最好”的算法，指的是最適合當(dāng)前場景的算法。通常情況下，挑選算法主要考慮兩個方面，分別是：

• 執(zhí)行效率：根據(jù)算法編寫出的程序，執(zhí)行時間越短，效率就越高；

• 占用的內(nèi)存空間：不同算法編寫出的程序，執(zhí)行時占用的內(nèi)存空間也不相同。如果實(shí)際場景中僅能使用少量的內(nèi)存空間，就要優(yōu)先選擇占用空間最少的算法。

算法只是解決問題的思路，無法直接在計(jì)算機(jī)上執(zhí)行。要想知道一個算法確切的執(zhí)行時間和占用的內(nèi)存大小，必須根據(jù)算法編寫出可執(zhí)行的程序。

當(dāng)算法的數(shù)量較少時（比如 2、3 種），我們確實(shí)可以編寫出各個算法對應(yīng)的程序，逐個在機(jī)器上運(yùn)行，記錄下各自的執(zhí)行時間和占用的內(nèi)存大小，然后挑選出“最好”的算法。但是，如果算法的數(shù)量很多（比如 10 種，20 種），真機(jī)測試的方法將不再適用，因?yàn)閷⒏鱾€算法一一編寫成程序的工作量是巨大的，得不償失。

實(shí)際開發(fā)中，往往采用 “預(yù)先估值”的方法挑選算法。具體來講，就是分析各個算法的實(shí)現(xiàn)過程（步驟），估算出它們各自的運(yùn)行時間和占用的內(nèi)存大小，就可以挑選出“最好”的算法。

我們習(xí)慣用「時間復(fù)雜度」預(yù)估算法的執(zhí)行時間，用「空間復(fù)雜度」預(yù)估算法占用的內(nèi)存大小。

時間復(fù)雜度

時間復(fù)雜度用來預(yù)估算法的執(zhí)行時間。

以解決“求 n 的階乘（n!）”為例，如下用偽代碼描述出了解決此問題的一種算法：

輸入 n? ? ? ? ? ? ?// 接收 n 的值

p <- 1? ? ? ? ? ? ?// p 的初值置為 1

for i<-1 to n：? ? // i 的值從 1 到 n，每次將 p*i 的值賦值給 p

? ? p <- p * i? ? ?

Print p? ? ? ? ? ? // 輸出 p 的值

偽代碼是一種介于自然語言和編程語言之間，專門用來描述算法的語言。偽代碼沒有固定的語法，本教程中我們用?<-?表示賦值過程，用?Print xxx?表示輸出某個變量的值。

接下來，我就以這個算法為例，教大家如何計(jì)算一個算法的時間復(fù)雜度。計(jì)算一個算法的時間復(fù)雜度，需要經(jīng)過以下 3 個步驟。

1) 統(tǒng)計(jì)算法中各個步驟的執(zhí)行次數(shù)

整個算法中共有 5 行偽指令，它們各自的執(zhí)行次數(shù)分別是：

輸入 n? ? ? ? ? ? ? ? ?<- 執(zhí)行 1 次

p <- 1? ? ? ? ? ? ? ? ?<- 執(zhí)行 1 次

for i<-1 to n：? ? ? ? <- i 的值從 1 遍歷到 n，當(dāng) i 的值為 n+1 的時候退出循環(huán)，總共執(zhí)行 n+1 次

? ? p <- p * i? ? ? ? ?<- i 從 1 到 n 的過程，共執(zhí)行 n 次

Print p? ? ? ? ? ? ? ? <- 執(zhí)行 1 次

所有偽指令執(zhí)行次數(shù)的總和是?2*n+4，顯然它不是一個固定值，整個表達(dá)式的大小取決于 n 的值。

2*n+4?可以直接作為算法執(zhí)行時間的估值，但通常情況下，我們會做進(jìn)一步地簡化，并用規(guī)范的格式來表示一個算法的執(zhí)行時間。

2) 簡化算法的執(zhí)行次數(shù)

通過統(tǒng)計(jì)各個算法中偽指令的執(zhí)行次數(shù)，每個算法的運(yùn)行時間都可以用類似 2*n+4、3*n^2+4*n+5 這樣的表達(dá)式表示。那么，該如何比較各個表達(dá)式的大小呢？

我們可以嘗試對每個表達(dá)式進(jìn)行簡化，簡化的方法是：假設(shè)表達(dá)式中變量的值無限大，去除表達(dá)式中那些對結(jié)果影響較小的項(xiàng)。

以 3*n^2+4*n+5 為例，簡化過程為：

1. 當(dāng) n 無限大時，3*n^2+4*n 與 3*n^2+4*n+5 的值非常接近，是否加 5 對表達(dá)式的值影響不大，因此表達(dá)式可以簡化為 3*n^2+4*n；

2. 當(dāng) n 無限大時，3*n^2?的值要遠(yuǎn)遠(yuǎn)大于 4*n 的值，它們之間類似于 10000 和 1 之間的關(guān)系，因此是否加 4*n 對表達(dá)式最終的值影響不大，整個表達(dá)式可以簡化為 3*n^2；

3. 當(dāng) n 無限大時，n^2?的值已經(jīng)超級大，是否乘 3 對最終結(jié)果影響不大，整個表達(dá)式可以簡化為? n^2。

基于“n 值無限大”的思想，3*n^2+4*n+5 最終就簡化成了 n^2。同樣的道理，2*n+4 可以簡化為 n。無論多么復(fù)雜的表達(dá)式，都可以采用這種方式進(jìn)行簡化。

3) 用大O記法表示算法的時間復(fù)雜度

除了用 n 外，一些人還可能會用 a、b、c 等字符作為表達(dá)式中的變量。為此，人們逐漸達(dá)成了一種共識，即都用 n 作為表達(dá)式中的變量，并采用大 O 記法表示算法的執(zhí)行時間。

采用大 O 記法表示算法的執(zhí)行時間，直接套用如下的格式即可：

O(頻度)

頻度指的就是簡化后的表達(dá)式。

采用大 O 記法，2*n+4 可以用O(n)表示，3*n^2+4*n+5 可以用O(n^2)表示。如果一個算法對應(yīng)的表達(dá)式中沒有變量（比如 10，100 等），則用O(1)表示算法的執(zhí)行時間。

如果一個算法的執(zhí)行時間最終估算為 O(n)，那么該算法的時間復(fù)雜度就是 O(n)。如下列舉了常用的幾種時間復(fù)雜度以及它們之間的大小關(guān)系：

O(1)< O(logn) < O(n) < O(n^2) < O(n^3) < O(2^n)

O(1)是最小的，對應(yīng)的算法的執(zhí)行時間最短，執(zhí)行效率最高。

空間復(fù)雜度

空間復(fù)雜度用來估算一個算法執(zhí)行時占用的內(nèi)存大小。

執(zhí)行過程中的程序，占用的內(nèi)存空間主要包括：

• 程序代碼本身所占用的存儲空間；

• 如果需要輸入輸出數(shù)據(jù)，也會占用一定的存儲空間；

• 運(yùn)行過程中，可能還需要臨時申請更多的存儲空間。

程序自身占用的存儲空間取決于編寫的代碼量，如果想壓縮這部分存儲空間，要求我們在實(shí)現(xiàn)功能的同時盡可能編寫足夠短的代碼。

程序運(yùn)行過程中輸入輸出的數(shù)據(jù)，往往由要解決的問題而定，即便所用算法不同，程序輸入輸出所占用的存儲空間也是相近的。

事實(shí)上，對算法的空間復(fù)雜度影響最大的，是程序運(yùn)行過程中臨時申請的內(nèi)存空間。不同算法編寫出的程序，運(yùn)行時申請的臨時存儲空間通常會有較大不同。

因此，比較各個算法占用的內(nèi)存大小，本質(zhì)上比較的是它們執(zhí)行過程中額外申請的內(nèi)存空間的大小。舉個簡單的例子：輸入 n A[1...n] <- {1...n} ? ?<- 額外申請 n 個空間根據(jù) n 的值，算法執(zhí)行時需要申請 n 個整數(shù)的內(nèi)存空間，n 的值越大，額外申請的內(nèi)存空間就越多。

和時間復(fù)雜度一樣，空間復(fù)雜度也習(xí)慣用大 O 記法表示。空間復(fù)雜度的估算方法是：

• 如果算法中額外申請的內(nèi)存空間不受用戶輸入值的影響（是一個固定值），那么該算法的空間復(fù)雜度用O(1)表示；

• 如果隨著輸入值 n 的增大，算法申請的存儲空間成線性增長，則程序的空間復(fù)雜度用O(n)表示;

• 如果隨著輸入值 n 的增大，程序申請的存儲空間成 n^2?關(guān)系增長，則程序的空間復(fù)雜度用O(n^2)表示；

• 如果隨著輸入值 n 的增大，程序申請的存儲空間成 n^3?關(guān)系增長，則程序的空間復(fù)雜度用O(n^3)表示；

多數(shù)場景中，挑選 "好" 算法往往更注重的是時間復(fù)雜度，空間復(fù)雜度只要處于一個合理的范圍即可。