時間、空間複雜度

上一篇文章的結尾提到如何評定一個好的演算法。如果對演算法還不是很了解的話，建議閱讀一下上一篇文章演算法，無處不在。

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

在通常情況下，時間複雜度和空間複雜度呈下圖的關係

也就是說當省空間意味著增加時間，省時間意味著增加空間。

hash演算法就是典型的用空間換時間；冒泡排序相對於桶排序用時間換空間（當然了還有更優的演算法，比如快速排序）。

這些演算法將在以後的文章里再向大家介紹。

時間複雜度

時間複雜度是指執行演算法所需要的計算工作量，也就是演算法運行需要的時間。我們一起來看一下下面的一小段代碼。

int sum = 0; //運行 1 次

int total = 0; //運行 1 次

for(int i = 1; i

sum = sum+i; //運行 n 次

for(int j = 1; j

total = total+i*j; //運行 n*n 次

}

把所有語句的次數全部加在一起，我們就可以得到一個函數，我們用T(n)表示：

T(n) = 1+1+n+n+n*n+n*n

T(n) = 2n^2+2n+2

這個時候我們就得到了該程序的執行次數，T(n)。通常情況下，運行時間主要取決於第一項（即n^2這一項），其他項可以忽略。這個時候我們就可以得到時間複雜度O，

O( f(n) ) = O(n^2)

所以，這個程序的時間複雜度為 n^2 ( n 的二次冪）。

對於f(n)的解釋在下面有一部分小字內容，可以不要求完全理解，如果看的不是很懂，那麼可以直接略過，不影響後文閱讀。

會有某個輔助函數f(n),使得當n趨近於無窮大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度。

n^2又是一個什麼概念呢？既然是函數，那就一定會有圖像，我們來通過下面的一張圖片，來了解一下n^2及其他時間複雜度圖像的趨勢

空間複雜度

空間複雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。演算法佔用的儲存空間包括：

輸入/輸出數據；

演算法本身；

額外需要的輔助空間。

輸入/輸出數據佔用的空間是必須的，演算法本身佔用的空間可壓縮量也是很小的，可以忽略不計，一般將演算法的輔助空間作為衡量空間複雜度的標準。

我們一起來看一下下面的函數。

void swap (int &a,int &b) {

int temp; //temp為輔助空間

temp = a;

a = b;

b = temp;

}

這個演算法使用了一個輔助空間temp，所以它的空間複雜度為O(1)。

大部分OJ的題目里都會標明時間限制和空間限制，評測結果如果出現TLE或MLE就說明時間超限或空間超限，儘可能的優化自己的演算法是必要的。

有關時間複雜度和空間複雜度的內容就介紹到這了，由於小編的水平有限，文中可能有一些待改進的地方，希望大家提出寶貴意見！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！