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

一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度兩部分來考慮。

在通常情況下，時間復(fù)雜度和空間復(fù)雜度呈下圖的關(guān)系

也就是說當(dāng)省空間意味著增加時間，省時間意味著增加空間。

hash算法就是典型的用空間換時間；冒泡排序相對于桶排序用時間換空間（當(dāng)然了還有更優(yōu)的算法，比如快速排序）。

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

時間復(fù)雜度

    時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，也就是算法運(yùn)行需要的時間。我們一起來看一下下面的一小段代碼。

int sum = 0;                                    //運(yùn)行 1 次

int total = 0;                                    //運(yùn)行 1 次

for(int i = 1; i <= n; i++) {                //運(yùn)行 n 次

    sum = sum+i;                             //運(yùn)行 n 次

    for(int j = 1; j <= n; j++)              //運(yùn)行 n*n 次

        total = total+i*j;                      //運(yùn)行 n*n 次

}

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

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

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

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

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

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

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

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

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

當(dāng) n = 10000 時，O(n) = 10000，O(n^2） = 100000000，O(n^3) = 1000000000000。由此可見，時間復(fù)雜度的控制是多么重要??！

空間復(fù)雜度

    空間復(fù)雜度是對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度。算法占用的儲存空間包括：

1. 輸入/輸出數(shù)據(jù)；

2. 算法本身；

3. 額外需要的輔助空間。

輸入/輸出數(shù)據(jù)占用的空間是必須的，算法本身占用的空間可壓縮量也是很小的，可以忽略不計，一般將算法的輔助空間作為衡量空間復(fù)雜度的標(biāo)準(zhǔn)。

    我們一起來看一下下面的函數(shù)。

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

    int temp;        //temp為輔助空間

    temp = a;

    a = b;

    b = temp;

}

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

大部分OJ的題目里都會標(biāo)明時間限制和空間限制，評測結(jié)果如果出現(xiàn)TLE或MLE就說明時間超限或空間超限，盡可能的優(yōu)化自己的算法是必要的。

有關(guān)時間復(fù)雜度和空間復(fù)雜度的內(nèi)容就介紹到這了，由于小編的水平有限，文中可能有一些待改進(jìn)的地方，希望大家提出寶貴意見！