資料結構01 演算法的時間複雜度和空間複雜度

作者：nnngu

GitHub：

https：//

github。com/nnngu

部落格園：http：//www。cnblogs。com/nnngu

簡書：

https：//www。

jianshu。com/users/1df20

d76ea5c

知乎：

https：//www。

zhihu。com/people/nnngu/

posts

1、演算法的概念：

演算法 （Algorithm），是對特定問題求解步驟的一種描述。

解決一個問題往往有不止一種方法，演算法也是如此。那麼解決特定問題的多個演算法之間如何衡量它們的優劣呢？有如下的指標：

2、衡量演算法的指標：

（1）時間複雜度：

執行這個演算法需要消耗多少時間。

（2）空間複雜度：

這個演算法需要佔用多少記憶體空間。

同一個問題可以用不同的演算法解決，而一個演算法的優劣將影響到演算法乃至程式的效率。演算法分析的目的在於為特定的問題選擇合適演算法。

一個演算法的評價主要從時間複雜度和空間複雜度來考慮

。

演算法在時間的高效性和空間的高效性之間通常是矛盾的

。所以一般只會取一個平衡點。通常我們假設程式執行在足夠大的記憶體空間中，

所以研究更多的是演算法的時間複雜度。

3、演算法的時間複雜度

（1）語句頻度T(n)：

一個演算法執行所花費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。

而且一個演算法花費的時間與演算法中的基本操作語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多

。一個演算法中的語句執行次數稱為語句頻度，記為T（n）。

（2）時間複雜度：

在剛才提到的語句頻度中，n稱為問題的規模，當n不斷變化時，語句頻度T（n）也會不斷變化。但有時我們想知道它的變化呈現什麼規律。為此，我們引入時間複雜度概念。 一般情況下，演算法中的基本操作語句的重複執行次數是問題規模n的某個函式，用T（n）表示，若有某個輔助函式f（n），使得當n趨近於無窮大時，T（n） / f（n） 的極限值為不等於零的常數，則稱f（n）是T（n）的同數量級函式。記作 T（n）=Ｏ（ f（n） ），稱Ｏ（ f（n） ） 為演算法的漸進時間複雜度，簡稱時間複雜度。 T（n） 不同，但時間複雜度可能相同。 如：T（n）=n²+5n+6 與 T（n）=3n²+3n+2 它們的T（n） 不同，但時間複雜度相同，都為O（n²）。

（3）常見的時間複雜度有：

常數階O（1），對數階O（log2n），線性階O（n），線性對數階O（nlog2n），平方階O（n2），立方階O（n3）， k次方階O（nk），指數階O（2n）。隨著問題規模n的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。

（4）平均時間複雜度和最壞時間複雜度：

平均時間複雜度是指所有可能的輸入例項均以等機率出現的情況下，該演算法的執行時間。

最壞情況下的時間複雜度稱最壞時間複雜度。一般討論的時間複雜度均是最壞情況下的時間複雜度。

這樣做的原因是：最壞情況下的時間複雜度是演算法在任何輸入例項上執行時間的界限，這就保證了演算法的執行時間不會比最壞情況更長。

（5）如何求時間複雜度：

【1】如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間複雜度是O（1）。

public static void main（String［］ args） {

int x = 91；

int y = 100；

while （y > 0） {

if （x > 100） {

x = x - 10；

y——；

} else {

x++；

}

}

}

該演算法的時間複雜度為：O（1）

這個程式看起來有點嚇人，總共迴圈運行了1100次，但是我們看到n沒有？

沒。這段程式的執行是和n無關的，就算它再迴圈一萬年，我們也不管他，只是一個常數階的函式

【2】當有若干個迴圈語句時，演算法的時間複雜度是由巢狀層數最多的迴圈語句中最內層語句的頻度f（n）決定的。

1 int x = 1；

2 for （int i = 1； i <= n； i++） {

3 for （int j = 1； j <= i； j++） {

4 for （int k = 1； k <= j； k++） {

5 x++；

6 }

7 }

8 }

該演算法的時間複雜度為：O（n3） 該程式段中頻度最大的語句是第5行的語句，內迴圈的執行次數雖然與問題規模n沒有直接關係，但是卻與外層迴圈的變數取值有關，而最外層迴圈的次數直接與n有關，因此該程式段的時間複雜度為 O（n3）

【3】演算法的時間複雜度不僅僅依賴於問題的規模，還與輸入例項的初始狀態有關。 在數值 A［n-1，n-2 。。。0］ 中查詢給定值k的演算法大致如下：

1 int i = n - 1；

2 while （i >= 0 && （A［i］ ！= k）） {

3 i——；

4 }

5 return i；

該演算法的時間複雜度為：O（n）

此演算法中第3行語句的頻度不僅與問題規模n有關，還與輸入例項A中的各元素取值和k的取值有關：如果A中沒有與k相等的元素，那麼第3行語句的頻度為 f（n）=n ，該程式段的時間複雜度為 O（n）

（6）用時間複雜度來評價演算法的效能

用兩個演算法A1和A2求解同一問題，時間複雜度分別是O（100n2），O（5n3）

（1） 5n3/100n2=n/20 ，當輸入量n＜20時，100n2> 5n3 ，這時A2花費的時間較少。

（2）隨著問題規模n的增大，兩個演算法的時間開銷之比 5n3/100n2=n/20 也隨著增大。即當問題規模較大時，演算法A1比演算法A2要高效的多。

它們的漸近時間複雜度O(n2)和O(n3) 評價了這兩個演算法在時間方面的效能。在演算法分析時，往往對演算法的時間複雜度和漸近時間複雜度不予區分

，而經常是將漸近時間複雜度 O（f（n）） 簡稱為時間複雜度，其中的f（n）一般是演算法中頻度最大的語句頻度。

4、演算法的空間複雜度

空間複雜度(Space Complexity) 是對一個演算法在執行過程中臨時佔用儲存空間大小的量度，記做 S(n)=O(f(n)) ，其中n為問題的規模

。利用演算法的空間複雜度，可以對演算法的執行所需要的記憶體空間有個預先估計。

一個演算法執行時除了需要儲存本身所使用的指令、常數、變數和輸入資料外，還需要一些對資料進行操作的工作單元和儲存一些計算所需的輔助空間。演算法執行時所需的儲存空間包括以下兩部分。

（1）固定部分。這部分空間的大小與輸入/輸出的資料的個數、數值無關。主要包括指令空間（即程式碼空間）、資料空間（常量、簡單變數）等所佔的空間。這部分屬於靜態空間。

（2）可變空間，這部分空間的主要包括動態分配的空間，以及遞迴棧所需的空間等。這部分的空間大小與演算法有關。

舉例分析演算法的空間複雜度：

public void reserse（int［］ a， int［］ b） {

int n = a。length；

for （int i = 0； i < n； i++） {

b［i］ = a［n - 1 - i］；

}

}

上方的程式碼中，當程式呼叫 reserse（） 方法時，要分配的記憶體空間包括：引用a、引用b、區域性變數n、區域性變數i

因此 f（n）=4 ，4為常量。所以該演算法的空間複雜度 S（n）=O（1）

5、總結

演算法的時間複雜度和兩個因素有關：演算法中的最大巢狀迴圈層數；最內層迴圈結構中迴圈的次數。

一般來說，具有多項式時間複雜度的演算法是可以接受的；具有指數（不是對數）時間複雜度的演算法，只有當n足夠小時才可以使用。一般效率較好的演算法要控制在O（log2n） 或者 O（n）